Advertisement
Guest User

Spoj Brackets

a guest
Sep 26th, 2014
199
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <string.h>
  5. using namespace std;
  6. struct node {
  7.     int left,right,parent,next;
  8.     bool hai,done;
  9.  
  10. };
  11. int current;
  12. node tree[10000000]={0};
  13. int index1;
  14. int make_tree(int c,int current)
  15. {
  16.     if (current-c<=1){index1=c;return 0;}
  17.     int lenori(current);
  18.     for (;c<lenori;c++)
  19.     {
  20.         if (tree[c].done==true)continue;
  21.         if (c<lenori-1){
  22.             tree[current].left=max(tree[c].left-tree[c+1].right,0)+tree[c+1].left;
  23.             tree[current].right=max(0,tree[c+1].right-tree[c].left)+tree[c].right;
  24.            
  25.             tree[c].done=tree[c+1].done=true;
  26.             tree[c].parent=tree[c+1].parent=current;
  27.             tree[c].next=c+1;
  28.             tree[c+1].next=c;
  29.         }
  30.         else
  31.         {
  32.             tree[current].left=tree[c].left;
  33.             tree[current].right=tree[c].right;
  34.             tree[c].parent=current;
  35.             tree[c].next=c;
  36.         }
  37.         current++;
  38.     }
  39.     make_tree(lenori,current);
  40. return 0;
  41. }
  42. int update_tree(int index1)
  43. {
  44.     swap(tree[index1].left,tree[index1].right);
  45.    for (;tree[index1].parent!=0;index1=tree[index1].parent)
  46.    {
  47.        if (tree[index1].next<index1)
  48.        {
  49.            tree[tree[index1].parent].left=max(tree[tree[index1].next].left-tree[index1].right,0)+tree[index1].left;
  50.             tree[tree[index1].parent].right=max(0,tree[index1].right-tree[tree[index1].next].left)+tree[tree[index1].next].right;
  51.        }
  52.        else
  53.        {
  54.            tree[tree[index1].parent].left=max(tree[index1].left+tree[index1+1].left-tree[index1+1].right,0);
  55.             tree[tree[index1].parent].right=max(0,tree[index1].right+tree[index1+1].right-tree[index1].left);
  56.        }
  57.  
  58.    }
  59. }
  60. int main()
  61. {
  62.     for (int io(0);io<10;io++){
  63. memset(tree,0,sizeof(tree[0])*10000000);
  64.     int dum;scanf("%d",&dum);
  65.     char a[30001];
  66.  
  67.     scanf("%s",a);
  68.     int n;
  69.     scanf("%d",&n);
  70. for (int c(0);c<strlen(a);c++,current=c)
  71. {
  72. if (a[c]==')'){tree[c].right=1;tree[c].hai=true;}
  73. else {tree[c].left=1;tree[c].hai=true;}
  74. }
  75. make_tree(0,strlen(a));
  76.  
  77.  
  78.  
  79.   for (int c(0);c<n;c++)
  80.   {
  81.       int ab;
  82.       scanf("%d",&ab);
  83.       if (ab==0){if (tree[index1].left==tree[index1].right&&tree[index1].left==0)printf("YES\n") ; else printf("NO\n") ;}
  84.       else
  85.       {
  86.  
  87.           update_tree(ab-1);
  88.           //print();
  89.       }
  90.   }
  91.     }
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement