fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<malloc.h>
  5. using namespace std;
  6. char s[30009];
  7. struct seg_node
  8. {
  9.     int nol;
  10.     int ncr;
  11. }st[100009];
  12. seg_node *merge(seg_node *l,seg_node *r)
  13. {
  14.     seg_node *rt=new seg_node();
  15.     int k1=l->ncr - r->nol;
  16.     int k2,k3;
  17.     if(k1>0)
  18.     {
  19.         k3=k1;
  20.         k2=0;
  21.     }
  22.     else
  23.     {
  24.         k2=-k1;
  25.         k3=0;
  26.     }
  27.     rt->nol=l->nol+k2;
  28.     rt->ncr=k3+r->ncr;
  29.     return rt;
  30. }
  31. void init(int idx,int l,int r)
  32. {
  33.     if(l==r)
  34.     {
  35.         if(s[l]=='(')
  36.         {
  37.           st[idx].nol=0;
  38.           st[idx].ncr=1;
  39.         }
  40.         else if(s[r]==')')
  41.         {
  42.           st[idx].nol=1;
  43.           st[idx].ncr=0;
  44.         }
  45.  
  46.         return ;
  47.     }
  48.     int mid=(l+r)/2;
  49.  
  50.     init(2*idx,l,mid);
  51.     init(2*idx+1,mid+1,r);
  52.     seg_node *sn=merge(&st[2*idx],&st[2*idx+1]);
  53.     st[idx].ncr=sn->ncr;
  54.     st[idx].nol=sn->nol;
  55.     free(sn);
  56. }
  57.  
  58. void update(int idx,int l,int r,int k)
  59. {
  60.     if(l==r && l==k)
  61.     {
  62.         if(s[k]==')')
  63.         {
  64.             s[k]='(';
  65.             st[idx].nol=0;
  66.             st[idx].ncr=1;
  67.         }
  68.         else
  69.         {
  70.             s[k]=')';
  71.             st[idx].nol=1;
  72.             st[idx].ncr=0;
  73.         }
  74.         return ;
  75.     }
  76.     int mid=(l+r)/2;
  77.     if(k<=mid) update(2*idx,l,mid,k);
  78.     else if(k>mid) update(2*idx+1,mid+1,r,k);
  79.  
  80.     seg_node *sn=merge(&st[2*idx],&st[2*idx+1]);
  81.     st[idx].ncr=sn->ncr;
  82.     st[idx].nol=sn->nol;
  83.     free(sn);
  84.  
  85. }
  86.  
  87. void check()
  88. {
  89.     if(st[1].nol==0 && st[1].ncr==0)
  90.     {
  91.         printf("YES\n");
  92.         return;
  93.     }
  94.     printf("NO\n");
  95.     return ;
  96. }
  97. int main()
  98. {
  99.     int t=10,n,q,k,i=0;;
  100.     while(t--)
  101.     {
  102.         scanf("%d",&n);
  103.  
  104.         scanf("%s",s+1);
  105.         i++;
  106.         printf("Test %d:\n",i);
  107.         if(n%2==0)
  108.         init(1,1,n);
  109.         scanf("%d",&q);
  110.         while(q--)
  111.         {
  112.             scanf("%d",&k);
  113.             if(n%2)
  114.             {
  115.                 printf("NO\n");
  116.                 continue;
  117.             }
  118.  
  119.             if(k==0)
  120.                 check();
  121.             else
  122.                 update(1,1,n,k);
  123.         }
  124.         if(t==0)
  125.             break;
  126.     }
  127.     return 0;
  128. }
  129.  
  130.  
Runtime error #stdin #stdout 0s 11768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KoS1ZU
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

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!