JOIN
Get Time
forums  Revision History
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 <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#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.