fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. struct node{
  5. ll sum,min;
  6. }
  7. tree[3*100005];
  8. char s[100005];
  9. void build(ll node, ll st, ll ed){
  10.     if(st==ed){
  11.         if(s[st]=='('){
  12.             tree[node].sum=tree[node].min=1;
  13.         }
  14.         else{
  15.             tree[node].sum=tree[node].min=-1;
  16.         }
  17.         return;
  18.     }
  19.     ll mid=(st+ed)/2;
  20.     build(node*2,st,mid);
  21.     build(node*2+1,mid+1,ed);
  22.     tree[node].sum=tree[node*2].sum + tree[node*2+1].sum;
  23.     tree[node].min=min(tree[2*node].min,tree[2*node].min+tree[node*2+1].min);
  24. }
  25. void update(ll node,ll st,ll ed,ll pos){
  26.     if(st==pos && ed==pos){
  27.         tree[node].sum=-tree[node].sum;
  28.         tree[node].min=-tree[node].sum;
  29.         return ;
  30.     }
  31.         ll mid = (st + ed) / 2;
  32.         if(st <= pos and pos <= mid)
  33.             update(2*node, st, mid, pos);
  34.         else
  35.             update(2*node+1, mid+1, ed, pos);
  36.  
  37.         tree[node].sum=tree[2*node].sum + tree[2*node+1].sum;
  38.         tree[node].min=min(tree[2*node].min, tree[2*node].min + tree[2*node+1].min);
  39. }
  40. int main()
  41. {
  42.     ll n,q,i,x,op,t=1;
  43.     while(scanf("%lld",&n)==1){
  44.             printf("Test %lld:\n",t++);
  45.             scanf("%s",s);
  46.             build(1,0,n-1);
  47.             scanf("%lld",&q);
  48.             for(i=0;i<q;i++){
  49.                 scanf("%lld",&op);
  50.                 if(op==0){
  51.                     if(tree[1].sum==0 && tree[1].min==0)
  52.                          printf("YES\n");
  53.                     else
  54.                         printf("NO\n");
  55.                 }
  56.                 else{
  57.                     update(1,0,n-1,op-1);
  58.                 }
  59.             }
  60.     }
  61.     return 0;
  62. }
  63.  
  64.  
Success #stdin #stdout 0s 8256KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/r4V84a
problem BRCKTS, based on SPOJ submission 17759112 (C++14), 2016-09-22 04:55:04
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!