fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5.  
  6. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  7. using namespace std;
  8. #define ll long long
  9. #define mod 1000000007
  10. #define pb push_back
  11. #define mp make_pair
  12. #define deb(x) cout<<#x<<" : "<<x<<"\n";
  13. #define debug(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\n";
  14. #define ff first
  15. #define ss second
  16. #define ub upper_bound
  17. #define lb lower_bound
  18. #define all(a) (a).begin(),(a).end()
  19. #define bs binary_search
  20. #define SZ(x) (int)(x).size()
  21. #define vi vector<int>
  22. #define pii pair<int,int>
  23. #define pll pair<ll,ll>
  24. #define ld long double
  25. //#define clr fflush(stdout)
  26. #define clr cout.flush();
  27. #define N 100001
  28. #define fpr(i,a,b) for(int i=a;i<b;i++)
  29. #define fdr(i,a,b) for(int i=a;i>b;i--)
  30. #define repp(i,a,b,d) for(int i=a;i<b;i+=d)
  31. #define repd(i,a,b,d) for(int i=a;i>b;i-=d)
  32. #define LLMIN LLONG_MIN
  33. #define LLMAX LLONG_MAX
  34. #define AKASH_PATEL ios_base::sync_with_stdio(false);
  35. #define SVNIT_SURAT cin.tie(NULL);cout.tie(NULL);
  36. #define mset(x,a) memset(x,a,sizeof(x));
  37. #define nl cout<<'\n';
  38. #define print(c) cout<<c<<'\n';
  39. #define setp(n) cout << fixed << setprecision(n)
  40. #define take_arr(a,n) fpr(i,0,n) cin>>a[i];
  41. #define print_arr(a,n) for(int i=0;i<n;i++) {cout<<a[i]<<" ";} cout<<'\n';
  42. #define take_mat(mat,n,m) fpr(i,0,n) fpr(j,0,m) cin>>mat[i][j];
  43. #define set_mat(mat,n,m,k) fpr(i,0,n) fpr(j,0,m) mat[i][j]=k;
  44. #define print_mat(dist,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<dist[i][j]<<" ";}cout<<'\n';}
  45. ll t[2*N],mn[2*N],st[2*N];
  46. ll n;
  47. void take_seg()
  48. {
  49.     fpr(i,0,n)
  50.     {
  51. //        cin>>t[n+i];
  52.         char c;
  53.         cin>>c;
  54.         //deb(c)
  55.         if(c=='(')
  56.         {
  57.             t[n+i]=mn[n+i]=1;
  58.         }
  59.         else
  60.         {
  61.             t[n+i]=mn[n+i]=-1;
  62.         }
  63.     }
  64. }
  65. void build()
  66. {
  67.     fdr(i,n-1,0)
  68.     {
  69.         t[i]=t[(i<<1)]+t[(i<<1)^1];
  70.         int l=(i<<1);
  71.         int r=(i<<1)^1;
  72.         if (st[l]>st[r])
  73.         {
  74.             swap(l,r);
  75.         }
  76.         mn[i]=min(mn[l],t[l]+mn[r]);
  77.     }
  78. }
  79. void update(ll idx,ll val)
  80. {
  81.     for(t[idx+=n]=val;idx>1;idx>>=1)
  82.     {
  83.         t[idx>>1]=t[idx]+t[idx^1];
  84. //        if(idx<(idx^1))
  85. //        mn[idx>>1]=min(mn[idx],t[idx]+mn[idx^1]);
  86. //        else{
  87. //            mn[idx>>1]=min(mn[idx^1],t[idx^1]+mn[idx]);
  88. //        }
  89.         int l=idx;
  90.         int r=idx^1;
  91.         if(st[l]>st[r])
  92.         {
  93.             swap(l,r);
  94.         }
  95.         mn[idx>>1]=min(mn[l],t[l]+mn[r]);
  96.     }
  97. }
  98. ll query(ll l,ll r)
  99. {
  100.     ll res=0;
  101.     for(l+=n,r+=n;l<r;l>>=1,r>>=1)
  102.     {
  103.         if(l&1)
  104.         {
  105.             res+=t[l++];
  106.         }
  107.         if(r&1)
  108.         {
  109.             res+=t[--r];
  110.         }
  111.     }
  112.     return res;
  113. }
  114. int main()
  115. {
  116.     //AKASH_PATEL;
  117. //    SVNIT_SURAT;
  118. //    int cas=10;
  119.     fpr(i,1,11)
  120.     {
  121.  
  122.         cin>>n;
  123.         fpr(j,n,2*n)
  124.         {
  125.             st[j]=j-n;
  126.         }
  127.         fdr(j,n-1,0)
  128.         {
  129.             int l=2*j;
  130.             int r=2*j+1;
  131.             st[j]=min(st[l],st[r]);
  132.         }
  133. //        fpr(j,1,n)
  134. //        {
  135. //            cout<<st[j]<<" ";
  136. //        }
  137. //        nl;
  138.         take_seg();
  139.         build();
  140.         int q;
  141.         cin>>q;
  142. //        fpr(j,1,2*n)
  143. //        {
  144. //            cout<<t[j]<<" ";
  145. //        }
  146. //        nl;
  147. //        fpr(j,1,2*n)
  148. //        {
  149. //            cout<<mn[j]<<" ";
  150. //        }
  151. //        nl;
  152.         cout<<"Test "<<i<<":\n";
  153.         while (q--)
  154.         {
  155.             int val;
  156.             cin>>val;
  157.             if(val)
  158.             {
  159.                 mn[val-1+n]=-t[val-1+n];
  160.                 t[val-1+n]=-t[val-1+n];
  161.                 update(val-1,t[val-1+n]);
  162. //                fpr(j,1,2*n)
  163. //                {
  164. //                    cout<<t[j]<<" ";
  165. //                }
  166. //                nl;
  167.             } else
  168.             {
  169.                 if(t[1]==0 && mn[1]==0)
  170.                 {
  171.                     cout<<"YES\n";
  172.                 }
  173.                 else
  174.                 {
  175.                     cout<<"NO\n";
  176.                 }
  177.             }
  178.         }
  179.     }
  180.     return 0;
  181. }
  182.  
  183.  
  184. /*
  185. 8
  186. ((())))(
  187. 6
  188. 0
  189. 4
  190. 0
  191. 8
  192. 0
  193. 0
  194.  */
  195.  
Time limit exceeded #stdin #stdout 5s 4496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BDI8kg
language:
C++14 (gcc 8.3)
created:
4 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!