fork(5) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define    ll              long long int
  5. #define    rd(a)           cin>>a
  6. #define    pt(a)           cout<<a
  7. #define    pb              push_back
  8. #define    mp              make_pair
  9. #define    cl              endl
  10. #define    ifor(i,a,b)     for(i=a;i<=b;i++)
  11. #define    dfor(i,a,b)     for(i=a;i>=b;i--)
  12. #define    pii             pair<int,int>
  13. #define    sz              100000
  14. #define    mad             1000000007
  15.  
  16. struct nod {
  17.  
  18.     int ob;
  19.     int cb;
  20. };
  21.  
  22. struct nod tree[4*sz +5];
  23. char a[sz+5];
  24. int n;
  25.  
  26. void build(int node,int s,int e) {
  27.  
  28.     if(s==e) {
  29.  
  30.         if(a[s]=='(') {
  31.  
  32.             tree[node].ob=1;
  33.             tree[node].cb=0;
  34.         }
  35.         else {
  36.             tree[node].ob=0;
  37.             tree[node].cb=1;
  38.         }
  39.     }
  40.     else {
  41.  
  42.         int mid=(s+e)/2;
  43.  
  44.         build(2*node,s,mid);
  45.         build(2*node +1,mid+1,e);
  46.  
  47.         int mb=min(tree[2*node].ob,tree[2*node +1].cb);
  48.  
  49.         tree[node].ob=tree[2*node].ob + tree[2*node +1].ob -mb;
  50.         tree[node].cb=tree[2*node].cb + tree[2*node +1].cb -mb;
  51.     }
  52. }
  53.  
  54. void update(int node,int s,int e,int idx) {
  55.  
  56.     if(s==idx) {
  57.  
  58.         if(a[s]==')') {
  59.  
  60.             tree[node].ob=1;
  61.             tree[node].cb=0;
  62.             a[s]='(';
  63.         }
  64.         else {
  65.  
  66.             tree[node].ob=0;
  67.             tree[node].cb=1;
  68.             a[s]=')';
  69.         }
  70.     }
  71.     else {
  72.  
  73.         int mid=(s+e)/2;
  74.  
  75.         if(s<=idx && idx<=mid) {
  76.             update(2*node,s,mid,idx);
  77.         }
  78.         else {
  79.             update(2*node +1,mid+1,e,idx);
  80.         }
  81.  
  82.         int mb=min(tree[2*node].ob,tree[2*node +1].cb);
  83.  
  84.         tree[node].ob=tree[2*node].ob + tree[2*node +1].ob -mb;
  85.         tree[node].cb=tree[2*node].cb + tree[2*node +1].cb -mb;
  86.     }
  87. }
  88. int main() {
  89.  
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     cout.tie(0);
  93.  
  94.     int t;
  95.     int i,j,k;
  96.  
  97.     string s;
  98.     t=10;
  99.     for(k=1;k<=t;k++) {
  100.  
  101.         cin>>n;
  102.         cin>>s;
  103.         n=s.size();
  104.  
  105.         //cout<<"s="<<s<<"\n";
  106.  
  107.         for(i=0;i<n;i++) {
  108.  
  109.             if(s[i]==')') {
  110.                 a[i+1]=s[i];
  111.             }
  112.             else {
  113.                 a[i+1]=s[i];     // if(s[i]=='(')
  114.             }
  115.         }
  116.         build(1,1,n);
  117.  
  118.  
  119.         cout<<"Test "<<k<<":"<<"\n";
  120.         int q,d;cin>>q;
  121.         while(q--) {
  122.  
  123.             cin>>d;
  124.             if(d!=0) {
  125.                 update(1,1,n,d);
  126.             }
  127.             else {
  128.  
  129.                 if(tree[1].ob==0 && tree[1].cb==0) cout<<"YES\n";
  130.                 else cout<<"NO\n";
  131.             }
  132.         }
  133.     }
  134.  
  135.     return 0;
  136. }
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/u1oRVh
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 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!