JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Tutorial Discussions Binary Indexed Trees Re: SPOJ:BRCKTS Revision History (2 edits)
 Re: SPOJ:BRCKTS (response to post by dhoni) Hii Dhoni, I have implemented your approach and it seems right to me and giving correct answer on my test cases but getting wrong answer on http://www.spoj.com/problems/BRCKTS/Code is in edit.
 Re: SPOJ:BRCKTS (response to post by dhoni) Hii Dhoni, I have implemented your approach and it seems right to me and giving correct answer on my test cases but getting wrong answer on http://www.spoj.com/problems/BRCKTS/Code is in edit.```#include using namespace std; #define pii pair #define fi first #define se second pii tree[(1<<21)]; char str[1000000]; pii merge(pii a, pii b) { pii res; res.fi = a.fi+b.fi - min(a.se, b.fi); res.se = a.se+b.se - min(a.se, b.fi); if(res.fi == res.se) return make_pair(0, 0); return res; } void build(char *str, int v, int tx, int ty) { if(tx == ty) { if(str[tx] == '(') tree[v] = make_pair(0, 1); else tree[v] = make_pair(1, 0); return ; } int mid = (tx+ty)/2; build(str, 2*v+1, tx, mid); build(str, 2*v+2, mid+1, ty); tree[v] = merge(tree[2*v+1], tree[2*v+2]); } void Update(int v, int tx, int ty, int index) { if(tx == ty && tx == index) { if(tree[v].fi == 1) { tree[v] = make_pair(0, 1); }else tree[v] = make_pair(1, 0);   return ; } if(tx == ty && tx != index) return ; if(index <= (tx+ty)/2) Update(2*v+1, tx, (tx+ty)/2, index); if(index > (tx+ty)/2) Update(2*v+2, (tx+ty)/2+1, ty, index); tree[v] = merge(tree[2*v+1], tree[2*v+2]); } int main() { int t = 10; for(int T=1; T<=t; T++) { int n; scanf("%d", &n); scanf("%s", str); build(str, 0, 0, n-1); int Q; scanf("%d", &Q); printf("Test %d:\n", T); while(Q--) { int K; scanf("%d", &K); if(K == 0) { if(tree[0].fi == 0 && tree[0].se == 0) { printf("YES\n"); }else { printf("NO\n"); } }else { Update(0, 0, n-1, K-1); } } } return 0; } ```
 Re: SPOJ:BRCKTS (response to post by dhoni) Hii Dhoni, I have implemented your approach and it seems right to me and giving correct answer on my test cases but getting wrong answer on http://www.spoj.com/problems/BRCKTS/Code is in edit.