UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#192673#2037. asnow_trace1002636ms57136kbC++111.9kb2023-10-10 11:31:222023-10-10 12:12:18

answer

#include<bits/stdc++.h>
using namespace std;
char s[1000005];int n,q;
vector<pair<int,int> >query[1000005];
int ans[1000005],suf[1000005],pre[1000005],ex1[1000005],ex2[1000005];
void solve(int l,int r){
	if(l == r){
		for(int i =0;i<query[l].size();i++)ans[query[l][i].second] = 0;query[l].clear();return;
	}int mid = l+r>>1;
	solve(mid+1,r);int tot =0 ;
	pre[0] = suf[0] = ex1[0] = ex2[0] = 0;
	for(int i = mid;i>=l;i--){
		pre[mid-i+1] = pre[mid-i],ex1[mid-i+1] = ex1[mid-i];
		if(s[i] == ')'){
			tot++;
		}else{
			if(tot)tot--,pre[mid-i+1]+=2;
			else ex1[mid-i+1]++;
		}
	}tot = 0;
	for(int i = mid+1;i<=r;i++){
		suf[i-mid] = suf[i-mid-1],ex2[i-mid] = ex2[i-mid-1];
		if(s[i] == '(')tot++;
		else{
			if(tot)tot--,suf[i-mid]+=2;
			else ex2[i-mid]++;
		}
	}for(int i = mid;i>=l;i--){
		int cnt =0 ;
		for(int j = query[i].size()-1;j>=0;j--){
			if(query[i][j].first<=mid)break;cnt++;
			assert(query[i][j].first<=r);
			int rr = query[i][j].first;
			
			ans[query[i][j].second] = 2*min(ex1[mid-i+1],ex2[rr-mid])+pre[mid-i+1]+suf[rr-mid];
		//	cout << i << " " << query[i][j].first << " " << ans[query[i][j].second] << " " << mid << " " << pre[mid-i+1] << " " << suf[rr-mid] << endl;
		}for(int j =0;j<cnt;j++)query[i].pop_back();
	}solve(l,mid);
}inline void write(int x){
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}inline int read(){
	int x = 0;char c=  getchar();
	while(c<'0' or c>'9')c = getchar();
	while('0'<=c and c<='9')x = x*10+(c^48),c = getchar();
	return x;
}
signed main(){
//	freopen("in.txt","r",stdin);
	scanf("%s",s+1);q = read();n = strlen(s+1);
//	for(int i = 1;i<=n;i++)cout << s[i];cout << endl;
	for(int i = 1;i<=q;i++){
		int l = read(),r = read();
		query[l].push_back(make_pair(r,i));
	}for(int i = 1;i<=n;i++)sort(query[i].begin(),query[i].end());
	solve(1,n);
	for(int i = 1;i<=q;i++){
		write(ans[i]);putchar('\n');
	}
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 4ms
memory: 24680kb

input:

(()))())))(())()())()()))((((()()))((((()((())()))(()((((()(())(())(()))())()())()())(())(()()((((((...

output:

854
136
108
12
836
206
550
252
536
266
220
344
830
502
170
290
522
526
464
98
160
10
840
298
332
272...

result:

ok 1000 lines

Test #2:

score: 10
Accepted
time: 3ms
memory: 24684kb

input:

)))((()())((())((()()())())(((())())((()((())(())()((((((())))((()(()())))(()()(())())()))(()()))(((...

output:

30
22
96
382
252
154
386
56
434
102
590
456
114
56
346
252
324
12
138
184
320
52
380
470
64
476
40
4...

result:

ok 1000 lines

Test #3:

score: 10
Accepted
time: 6ms
memory: 24688kb

input:

(()((())))))))((())(()()))()))()()())(()))(())))))))(((())((((((((((()((()())()(()(())(()())(()))(((...

output:

674
192
100
168
206
244
378
746
184
196
196
602
414
302
224
358
232
482
154
448
168
704
232
232
810
...

result:

ok 1000 lines

Test #4:

score: 10
Accepted
time: 4ms
memory: 24684kb

input:

))))))))()))())()(()()())()())(((()())(((()(((()()))(()()()))())(()()(()()())()(())()())))))()((((()...

output:

168
378
240
380
548
324
54
492
724
276
184
398
66
452
404
192
192
594
192
128
918
424
516
46
108
430...

result:

ok 1000 lines

Test #5:

score: 10
Accepted
time: 9ms
memory: 24684kb

input:

((())))(()((()()))()))))((((()()()()()()()))()()(()(())(()((()))()((())))))()(((()())()))()())))(())...

output:

634
386
334
6
246
372
226
424
274
168
254
448
312
112
532
126
594
780
112
150
68
470
260
150
22
322
...

result:

ok 1000 lines

Test #6:

score: 10
Accepted
time: 0ms
memory: 24680kb

input:

))((()))()(())())(()()))))()()((((()()())()((())(())))))(())))()())()()(())()(())())(()())))(()()))(...

output:

728
224
580
200
784
152
280
194
0
664
278
260
630
328
816
470
388
736
82
132
406
440
140
12
276
776
...

result:

ok 1000 lines

Test #7:

score: 10
Accepted
time: 648ms
memory: 57136kb

input:

((((()))()()())(()))((()())(((())))(()((()))))))()()))()))((((()(()(()()()(()(())(()())))(((()())))(...

output:

142860
235344
446706
759772
134088
748980
83870
685562
31730
572204
366368
67746
18554
603330
946486...

result:

ok 1000000 lines

Test #8:

score: 10
Accepted
time: 657ms
memory: 57128kb

input:

())))()))))(()))()())(()(()))((()))))(()))((())()((()(()()((())(())()))(()))))())(((()(())()(())()()...

output:

583148
425884
255036
448502
200322
256890
167684
114904
55236
440164
138094
879918
580038
452166
984...

result:

ok 1000000 lines

Test #9:

score: 10
Accepted
time: 646ms
memory: 57128kb

input:

)()((()())(())())(()())))(((()())()()(((((()(()()(()(())(()())((()(((()()))()))))()(((())(((((()()()...

output:

47942
241400
323510
553980
111490
20570
51892
169422
82080
124416
107806
804528
123414
274334
135650...

result:

ok 1000000 lines

Test #10:

score: 10
Accepted
time: 659ms
memory: 57136kb

input:

())()()(()())))())())))))))(()((()()(((()))(()(())))(())))())(()((()))()))(()))()((((((())(())(())((...

output:

487878
425694
419984
176404
493462
782462
63276
27548
109942
308166
354282
302574
697816
3128
144748...

result:

ok 1000000 lines