added working NWERC11C
[the-user-spoj:the-user-spoj.git] / BRCKTS.cpp
1 #include <cstdio>
2 #include <cstdlib>
3 #include <stdint.h>
4 #include <string>
5 #include <iostream>
6 #include <unistd.h>
7 #include <sys/time.h>
8 #include <stack>
9 #include <vector>
10 #include <deque>
11 #include <cmath>
12 #include <algorithm>
13 #include <cstring>
14 using namespace std;
15
16 typedef unsigned long long ull;
17
18 inline FILE& operator>>(FILE& f, char*& d)
19 {
20     int s = 20;
21     d = (char*)malloc(s);
22     int chr;
23     int i = 0;
24     do
25     {
26         chr = fgetc(&f);
27         if(chr == EOF)
28             goto OPERATOR_RSHIFT_FILE_CHAR_PTR_end;
29     }
30     while(chr == '\n' || chr == '\r' || chr == '\t' || chr == ' ');
31     do
32     {
33         if(i == s)
34         {
35             s *= 2;
36             d = (char*)realloc(d, s);
37         }
38         d[i] = chr;
39         chr = fgetc(&f);
40         ++i;
41     }
42     while(chr != EOF && chr != '\n' && chr != '\r' && chr != '\t' && chr != ' ');
43     OPERATOR_RSHIFT_FILE_CHAR_PTR_end:;
44     d = (char*)realloc(d, i+1);
45     d[i] = '\0';
46     return f;
47 }
48 inline FILE& operator>>(FILE& f, char& chr)
49 {
50     int x;
51     do
52     {
53         x = fgetc(&f);
54         if(x == EOF)
55         {
56             chr = '\0';
57             return f;
58         }
59     }
60     while(x == '\n' || x == '\r' || x == '\t' || x == ' ');
61     chr = x;
62     return f;
63 }
64 inline FILE& operator>>(FILE& f, int& x)
65 {
66     char *d;
67     f >> d;
68     x = atoi(d);
69     free(d);
70     return f;
71 }
72 inline FILE& operator>>(FILE& f, ull& x)
73 {
74     fscanf(&f, "%llu", &x);
75     return f;
76 }
77 inline FILE& operator>>(FILE& f, float& x)
78 {
79     char *d;
80     f >> d;
81     x = atof(d);
82     free(d);
83     return f;
84 }
85 inline FILE& operator>>(FILE& f, double& x)
86 {
87     char *d;
88     f >> d;
89     x = atof(d);
90     free(d);
91     return f;
92 }
93 inline FILE& operator>>(FILE& f, long double& x)
94 {
95     fscanf(&f, "%LE", &x);
96     return f;
97 }
98 inline FILE& operator>>(FILE& f, string& str)
99 {
100     char *d;
101     f >> d;
102     str.~string();
103     new (&str) string(d);
104     free(d);
105     return f;
106 }
107 inline FILE& operator<<(FILE& f, const char *str)
108 {
109     fputs(str, &f);
110     return f;
111 }
112 inline FILE& operator<<(FILE& f, int x)
113 {
114     fprintf(&f, "%d", x);
115     return f;
116 }
117 inline FILE& operator<<(FILE& f, size_t x)
118 {
119     fprintf(&f, "%u", x);
120     return f;
121 }
122 inline FILE& operator<<(FILE& f, ull x)
123 {
124     fprintf(&f, "%llu", x);
125     return f;
126 }
127 inline FILE& operator<<(FILE& f, double x)
128 {
129     fprintf(&f, "%.12f", x);
130     return f;
131 }
132 inline FILE& operator<<(FILE& f, long double x)
133 {
134     fprintf(&f, "%.12Lf", x);
135     return f;
136 }
137 inline FILE& operator<<(FILE& f, const string& str)
138 {
139     f << str.c_str();
140     return f;
141 }
142 inline FILE& operator<<(FILE& f, char c)
143 {
144     fputc(c, &f);
145     return f;
146 }
147 struct _endofline
148 {
149 } eol;
150 struct _flush
151 {
152 } clearbuff;
153 inline FILE& operator<<(FILE& f, const __typeof__(eol)&)
154 {
155     fputc('\n', &f);
156 //     fflush(&f);
157     return f;
158 }
159 inline FILE& operator<<(FILE& f, const __typeof__(clearbuff)&)
160 {
161     fflush(&f);
162     return f;
163 }
164
165 FILE& lin(*stdin);  // low-level-in
166 FILE& lout(*stdout);    // low-level-out
167 FILE& lerr(*stderr);
168
169 typedef pair<int,int> PII;
170
171 struct node { int sum, tmin; };
172
173 node seg[65535] = {};
174
175 int n;
176 int limit;
177 int depth;
178
179 inline bool bottom(int x)
180 {
181     return x >= limit-1;
182 }
183
184 inline bool overflow(int x)
185 {
186     return x >= limit-1+n;
187 }
188
189 void buildSegs(int x)
190 {
191     if(bottom(x))
192         return;
193     buildSegs(2*x+1);
194     buildSegs(2*x+2);
195     node& s(seg[x]);
196     s.sum = seg[2*x+1].sum + seg[2*x+2].sum;
197     s.tmin = min(seg[2*x+1].tmin, seg[2*x+1].sum + seg[2*x+2].tmin);
198 }
199
200 void add(int x, int k, int a)
201 {
202 //     lerr << k << eol;
203     node& s(seg[x]);
204     if(bottom(x))
205     {
206         s.sum *= -1;
207         s.tmin = s.sum;
208     }
209     else
210     {
211         if(k & (1 << a))
212             add(2*x+2, k xor (1 << a), a-1);
213         else
214             add(2*x+1, k, a-1);
215         s.sum = seg[2*x+1].sum + seg[2*x+2].sum;
216         s.tmin = min(seg[2*x+1].tmin, seg[2*x+1].sum + seg[2*x+2].tmin);
217     }
218 }
219
220 void dump(int x, int d = 0)
221 {
222     if(overflow(x))
223         return;
224     for(int i = 0; i != d; ++i)
225         lerr << "  ";
226     lerr << x << " Min: " << seg[x].tmin << " Sum: " << seg[x].sum << eol;
227     dump(2*x+1, d+1);
228     dump(2*x+2, d+1);
229 }
230
231 int main()
232 {
233     int t = 10;
234     for(int _i = 0; _i != t; ++_i)
235     {
236         memset(seg, 0, 65535 * sizeof(node));
237         lout << "Test " << (_i+1) << ':' << eol;
238         lin >> n;
239         limit = 1;
240         depth = 0;
241         while(limit < n)
242         {
243             limit <<= 1;
244             ++depth;
245         }
246         string data;
247         lin >> data;
248         for(int i = limit-1; !overflow(i); ++i)
249         {
250             seg[i].tmin = (data[i-limit+1] == '(' ? 1 : -1);
251             seg[i].sum = seg[i].tmin;
252         }
253         buildSegs(0);
254         int m;
255         lin >> m;
256         for(int i = 0; i != m; ++i)
257         {
258             int k;
259             lin >> k;
260             if(k == 0)
261                 lout << (seg[0].tmin != 0 || seg[0].sum != 0 ? "NO\n" : "YES\n");
262             else if(k == -1)
263                 dump(0);
264             else
265                 add(0, k-1, depth-1);
266         }
267     }
268 }
269
270