SPOJ BRCKTS Solution

brckts.cpp

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 30000

int N, M;
int word[MAX_N];
int fenwick_sum[MAX_N + 1];
int fenwick_min[MAX_N + 1];
int word_sum;

void update(int ind, int val) {
	int prev_val = word[ind];
	word[ind] = val;
	word_sum += val - prev_val;
	for (int fen_ind = ind + 1; fen_ind <= N; fen_ind += fen_ind & -fen_ind) {
		fenwick_sum[fen_ind] += val - prev_val;
		int curr_min = word[fen_ind - 1];
		int lo = fen_ind - (fen_ind & -fen_ind);
		for (int curr_ind = fen_ind - 1; curr_ind > lo; 
				curr_ind -= curr_ind & -curr_ind) {
			curr_min += fenwick_sum[curr_ind];
			curr_min = min(curr_min, fenwick_min[curr_ind]);
		}
		fenwick_min[fen_ind] = curr_min;
	}
}

int query() {
	int ret = 30500;
	for (int i = N; i > 0; i -= i & -i) {
		ret += fenwick_sum[i];
		ret = min(ret, fenwick_min[i]);
	}
	return ret;
}

bool check() {
	return query() >= 0 && word_sum == 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	//freopen("spoj-brckts.in", "r", stdin);

	for (int tc = 1; tc <= 10; tc++) {
		cout << "Test " << tc << ":" << '\n';
		cin >> N;
		string w;
		cin >> w;
		for (int i = 0; i < N; i++) {
			word[i] = 0;
			fenwick_sum[i] = fenwick_min[i] = 0;
		}
		word_sum = 0;
		for (int i = 0; i < N; i++) {
			int curr_word = w[i] == '(' ? 1 : -1;
			update(i, curr_word);
		}
	
		cin >> M;
	
		for (int i = 0; i < M; i++) {
			int op;
			cin >> op;
			/* debug 
			cout << op << endl;
			for (int i = 0; i <= N; i++) {
				cout << fenwick_sum[i] << ' ' << fenwick_min[i] << '|';
			}
			cout << endl;
			*/
			
			if (op == 0) {
				cout << (check() ? "YES" : "NO") << '\n';
			}
			else {
				update(op - 1, -word[op - 1]);
			}
		}
	}

	cout.flush();
	return 0;
}