QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380406#1194. Parehtneses Editorthomas_li#AC ✓103ms29908kbC++171.5kb2024-04-07 03:08:492024-04-07 03:08:50

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 03:08:50]
  • 评测
  • 测评结果:AC
  • 用时:103ms
  • 内存:29908kb
  • [2024-04-07 03:08:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A, class B> void cmx(A& x, B y){ x = max<A>(x,y); }
template<class A, class B> void cmn(A& x, B y){ x = min<A>(x,y); }
typedef pair<int,int> pii;
typedef vector<int> vi;


signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	string s; cin >> s;
	vi psa = {0};
	vi ours;
	vi prv = {-1};
	map<int,vi> pos;
	pos[0].PB(0);
	int ptr = 0;
		

	int cum = 0;
	auto add = [&](int x){
		ptr++;
		// psa[n]-psa[l] = 0
		psa.PB(psa.back()+x);
		pos[psa.back()].PB(ptr);
		// psa[n] < psa[l-1]	
		int our_prv = -1;
		if(x < 0){
			our_prv = ptr-1;
		} else{
			int tmp = prv.back();
			if(tmp != -1) our_prv = prv[tmp];
		}
		int cnt = pos[psa.back()].end() - lower_bound(all(pos[psa.back()]),our_prv+1);
		cnt--; // ourselves
		ours.PB(cnt);	
		//cerr << ptr << " " << our_prv << " " << x << " " << psa.back() << " " << cnt << "\n";
		prv.PB(our_prv);
		cum += cnt;
	};
	auto pop = [&](){
		cum -= ours.back();
		int v = psa.back();
		psa.pop_back();
		prv.pop_back();
		pos[v].pop_back();
		ours.pop_back();
		ptr--;
	};
	for(char c : s){
		if(c == '-') pop();
		else add(c == '(' ? -1 : 1);
		cout << cum << "\n";
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

(()())---)

output:

0
0
1
1
3
4
3
1
1
2

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

()--()()----)(()()))

output:

0
1
0
0
0
1
1
3
1
1
0
0
0
0
0
1
1
3
4
4

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 3896kb

input:

))(((-)(()((---(-)(-())-(()()(-)--(())))--()((())-)(()(())((-))))(-(((()((()()()()))-(())((((--))-())-)(-(--))))((((-)(-(-)((((()--(---)(-))()(-)(()()-(())()(()()((()()))))(()(()(-(--)-()((()(((()-))-)(()-()()-(-((-)(-)(((()-)))))-())()-(()((()(-)()))((-))())))()()()(-(-(())-()(()-)-))((()))((--(-()...

output:

0
0
0
0
0
0
1
1
1
2
2
2
2
2
1
1
1
2
2
2
2
4
6
4
4
4
5
5
7
7
7
10
7
5
5
5
6
7
9
12
9
7
7
9
9
9
9
10
11
10
11
11
11
12
12
12
13
15
15
15
15
18
20
23
25
25
25
25
25
25
25
26
26
26
26
27
27
29
29
32
32
36
37
39
37
37
37
38
40
40
40
40
40
40
40
41
44
41
41
43
46
43
46
46
46
46
46
43
46
48
49
50
50
50
50
...

result:

ok 20000 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

(()())---)

output:

0
0
1
1
3
4
3
1
1
2

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

()--()()----)(()()))

output:

0
1
0
0
0
1
1
3
1
1
0
0
0
0
0
1
1
3
4
4

result:

ok 20 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

(

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

)

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

((

output:

0
0

result:

ok 2 number(s): "0 0"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

()

output:

0
1

result:

ok 2 number(s): "0 1"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

(-

output:

0
0

result:

ok 2 number(s): "0 0"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

)(

output:

0
0

result:

ok 2 number(s): "0 0"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

))

output:

0
0

result:

ok 2 number(s): "0 0"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

)-

output:

0
0

result:

ok 2 number(s): "0 0"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

(((((()((())()((()))

output:

0
0
0
0
0
0
1
1
1
1
2
3
3
5
5
5
5
6
7
10

result:

ok 20 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

(-)(--(-((-))-)-)-)(

output:

0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1

result:

ok 20 numbers

Test #16:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

))((()((-((()(()((((

output:

0
0
0
0
0
1
1
1
1
1
1
1
2
2
2
3
3
3
3
3

result:

ok 20 numbers

Test #17:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

))))--()-)))-)()))()

output:

0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
2
2
2
2
3

result:

ok 20 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

(-(()))-))())))(((--

output:

0
0
0
0
1
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3

result:

ok 20 numbers

Test #19:

score: 0
Accepted
time: 26ms
memory: 10552kb

input:

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

output:

0
1
1
1
1
1
1
1
2
3
4
4
4
5
5
7
9
10
10
10
10
10
11
12
12
12
12
13
13
13
14
14
14
14
15
16
16
16
16
17
18
20
22
22
22
23
26
26
30
30
30
31
31
33
33
33
33
34
34
36
37
37
39
42
47
49
49
52
52
52
53
53
55
55
55
56
56
58
61
61
65
69
69
74
74
80
81
81
83
83
86
86
86
86
87
87
89
89
92
92
96
96
96
96
97
97...

result:

ok 200000 numbers

Test #20:

score: 0
Accepted
time: 13ms
memory: 6340kb

input:

))--))--)(-(-((-)-))-(())----(-)))))--(-(-)((--)(-((-()--((()--(-)(----(-()()-)()-(()(()-(((((())))(()--()-)()-))-)))((())())-)-)-))((((((----))-)))-)(((((-))(--(---(-)--)---)-)((--(-(-)---)--)(--)()-)))-(-()(((--)-)())()(()(())(-((---()(--)))-(-()-)-(-((-)()(-(--((-))((--(()--))((-))(-)-(((---(()-(...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
2
4
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
2
1
1
1
1
2
2
2
1
1
1
1
1
1
2
2
4
2
4
4
7
4
4
4
5
5
5
6
5
5
5
5
5
5
5
6
7
8
9
9
9
10
9
9
9
10
9
10
10
12
10
12
14
12
14
15
16
16
16
16
17
18
18
20
22
20
22
20
22
20
22
23
23
23
23
...

result:

ok 200000 numbers

Test #21:

score: 0
Accepted
time: 39ms
memory: 9988kb

input:

(-)()--)(((-))((((---(()(--)((((-)()()-(()((()--(()-)((-((-(())()()((-((((((()()))-())--(-)((-)(((((()-(((-((-((-(-()-)(())-)-(()(-(((((()(-)(---(-(--))((((-(((-())(((()(-)))(()(((-((-)((-)()((-))(()((--(((((-((((---((-((()(()()-((()((-)(((-)))-)(--((--)()(()((())-))---)()-)(-((-(((((--(--(-(-)()-))...

output:

0
0
0
0
1
0
0
0
0
0
0
0
1
2
2
2
2
2
2
2
2
2
2
3
3
3
2
3
3
3
3
3
3
4
4
6
6
9
6
6
6
7
7
7
7
8
7
7
7
7
8
7
8
8
8
8
8
8
8
8
8
9
10
10
12
12
15
15
15
15
15
15
15
15
15
15
15
16
16
18
19
20
19
19
21
22
21
19
19
19
21
21
21
21
24
24
24
24
24
24
24
25
24
24
24
24
24
24
24
24
24
24
24
24
24
24
25
24
25
25
25...

result:

ok 200000 numbers

Test #22:

score: 0
Accepted
time: 40ms
memory: 9908kb

input:

((-))))(-----())--()-(()(()))((()-)))(--(())-())---)(-(()))()))()()-(--)))-)-()(-)(-)())()--)(-())--))))))))))-((--(-((((()()()))-)-)))()))()))--(()(-()---)-()-)()))-)----)-)))---(-)()-)-()()(-()()--()()(-)--(()()))-)()))(-)()(-)())--(()))))(-))()-(--)(-))--)(-)()()(-)(())--)(--))---)-()---))((())))...

output:

0
0
0
1
1
1
1
1
1
1
1
1
0
0
1
2
1
0
0
1
0
0
0
1
1
1
2
4
5
5
5
5
6
5
6
7
9
9
9
7
7
7
8
10
8
8
10
12
10
8
8
10
10
10
10
10
11
14
16
16
19
20
21
21
23
23
26
23
23
23
23
24
24
24
24
24
24
24
25
25
25
25
25
25
25
25
26
26
26
27
26
26
26
26
26
26
27
27
27
26
27
27
27
27
27
27
27
27
27
27
27
27
27
27
27
27...

result:

ok 200000 numbers

Test #23:

score: 0
Accepted
time: 26ms
memory: 7768kb

input:

()))))(()-(((((()-)())()(-((((--(((()(-())((-((-)())-)-))((--)()-(()())()()((---)((-)-(-)-()-)())-(((()-))((()-))(-()))(((--)-)-())())((-(((--)-(()))-)-))())((-()-(((((--)((-()())()(-()-))(((-))((-))-(((((-)(()()(())---(())))--)()()))()))()()-))()-(-(--)())--)-(-((()()(())-())-)())(()-))()(()-())(-)...

output:

0
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
2
1
2
2
4
5
5
7
7
7
7
7
7
7
7
7
7
7
7
7
8
8
8
8
10
11
11
11
11
11
11
11
12
12
14
16
14
16
14
16
17
17
17
17
17
18
18
20
18
18
18
19
19
21
22
22
24
24
27
27
27
27
27
24
27
27
27
27
31
27
27
27
31
27
27
28
27
28
28
30
34
30
30
30
30
30
31
30
31
32
32
32
32
33
32
33
34
3...

result:

ok 200000 numbers

Test #24:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

)()()()()()()()()()(

output:

0
0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45

result:

ok 20 numbers

Test #25:

score: 0
Accepted
time: 51ms
memory: 20244kb

input:

)(((((((((()((--)((((((-(((((((((()(()((-)(-()(((()((()(((((()-()-(((((((-()(((((((()((((((((((((((((((()((-())(((((())((((((((((((((((-((((((((((()())(((((()((((((((((--(((()()((()(((((((((-)((()((((((((-(((((((((((((((((((()(((((-)(((((()((()(((()((((((((()(((((((((((()(((((()-(((-(((((((((-((-)((...

output:

0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
4
4
4
4
6
6
6
6
9
9
9
9
9
10
10
10
10
11
11
11
11
11
11
11
12
11
11
12
11
11
11
11
11
11
11
11
11
11
12
12
12
12
12
12
12
12
12
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
14
14
14
14
14
15
17
17
17
17
17
17
17...

result:

ok 200000 numbers

Test #26:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

()()()()()()()()()()

output:

0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55

result:

ok 20 numbers

Test #27:

score: 0
Accepted
time: 51ms
memory: 19996kb

input:

())))))))-))))))))))))))-))))))))))))))()))))))))))))))())))))((()()))))-)))))()))))))))))))())()))))))-))-)(-)))()))(()))))))))))-))))-))-))--((()))))))))))))())))((-))-)))))))))-)))))))))()()-))-))))-)-()())))(())))))-)))))(()))-)(()))()))))))))()())(--)()))))))))))-)))))))))))))()))))))))-)()))))...

output:

0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
4
4
6
7
8
8
8
8
8
8
8
8
8
8
9
9
9
9
9
9
9
9
9
9
9
9
9
9
10
10
10
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
12
12
12
12
12
13
14
14
14
14
14
14
14
14
14
14
14
...

result:

ok 200000 numbers

Test #28:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

(((((((((())))))))))

output:

0
0
0
0
0
0
0
0
0
0
1
2
3
4
5
6
7
8
9
10

result:

ok 20 numbers

Test #29:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

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

output:

0
0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
...

result:

ok 2000 numbers

Test #30:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

))))))))))((((((((((

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 20 numbers

Test #31:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

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

output:

0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
90...

result:

ok 2000 numbers

Test #32:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 2000 numbers

Test #33:

score: 0
Accepted
time: 16ms
memory: 10612kb

input:

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

output:

0
0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
...

result:

ok 200000 numbers

Test #34:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 2000 numbers

Test #35:

score: 0
Accepted
time: 16ms
memory: 10612kb

input:

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

output:

0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
90...

result:

ok 200000 numbers

Test #36:

score: 0
Accepted
time: 75ms
memory: 19104kb

input:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200000 numbers

Test #37:

score: 0
Accepted
time: 77ms
memory: 19164kb

input:

))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200000 numbers

Test #38:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

)()()()()()()()()()(

output:

0
0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45

result:

ok 20 numbers

Test #39:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

()()()()()()()()()()

output:

0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55

result:

ok 20 numbers

Test #40:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

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

output:

0
0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
...

result:

ok 2000 numbers

Test #41:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

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

output:

0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
90...

result:

ok 2000 numbers

Test #42:

score: 0
Accepted
time: 20ms
memory: 10696kb

input:

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

output:

0
0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
...

result:

ok 200000 numbers

Test #43:

score: 0
Accepted
time: 8ms
memory: 10708kb

input:

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

output:

0
1
1
3
3
6
6
10
10
15
15
21
21
28
28
36
36
45
45
55
55
66
66
78
78
91
91
105
105
120
120
136
136
153
153
171
171
190
190
210
210
231
231
253
253
276
276
300
300
325
325
351
351
378
378
406
406
435
435
465
465
496
496
528
528
561
561
595
595
630
630
666
666
703
703
741
741
780
780
820
820
861
861
90...

result:

ok 200000 numbers

Test #44:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

((((((((((((((((((((

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 20 numbers

Test #45:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 2000 numbers

Test #46:

score: 0
Accepted
time: 103ms
memory: 29896kb

input:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200000 numbers

Test #47:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

))))))))))))))))))))

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 20 numbers

Test #48:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 2000 numbers

Test #49:

score: 0
Accepted
time: 92ms
memory: 29908kb

input:

))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200000 numbers

Test #50:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

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

output:

0
0
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
8
8
8
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
17
17
17
18
18
18
19
19
19
20
20
20
21
21
21
22
22
22
23
23
23
24
24
24
25
25
25
26
26
26
27
27
27
28
28
28
29
29
29
30
30
30
31
31
31
32
32
32
33
33
33
34
34
34
35
35
35
36
36
36...

result:

ok 1998 numbers

Test #51:

score: 0
Accepted
time: 4ms
memory: 4568kb

input:

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

output:

0
0
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
8
8
8
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
17
17
17
18
18
18
19
19
19
20
20
20
21
21
21
22
22
22
23
23
23
24
24
24
25
25
25
26
26
26
27
27
27
28
28
28
29
29
29
30
30
30
31
31
31
32
32
32
33
33
33
34
34
34
35
35
35
36
36
36...

result:

ok 19998 numbers

Test #52:

score: 0
Accepted
time: 82ms
memory: 16284kb

input:

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

output:

0
0
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
8
8
8
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
17
17
17
18
18
18
19
19
19
20
20
20
21
21
21
22
22
22
23
23
23
24
24
24
25
25
25
26
26
26
27
27
27
28
28
28
29
29
29
30
30
30
31
31
31
32
32
32
33
33
33
34
34
34
35
35
35
36
36
36...

result:

ok 199998 numbers

Test #53:

score: 0
Accepted
time: 62ms
memory: 12096kb

input:

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

output:

0
0
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
8
8
8
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
17
17
17
18
18
18
19
19
19
20
20
20
21
21
21
22
22
22
23
23
23
24
24
24
25
25
25
26
26
26
27
27
27
28
28
28
29
29
29
30
30
30
31
31
31
32
32
32
33
33
33
34
34
34
35
35
35
36
36
36...

result:

ok 199999 numbers

Test #54:

score: 0
Accepted
time: 66ms
memory: 12088kb

input:

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

output:

0
0
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
8
8
8
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
17
17
17
18
18
18
19
19
19
20
20
20
21
21
21
22
22
22
23
23
23
24
24
24
25
25
25
26
26
26
27
27
27
28
28
28
29
29
29
30
30
30
31
31
31
32
32
32
33
33
33
34
34
34
35
35
35
36
36
36...

result:

ok 199999 numbers

Test #55:

score: 0
Accepted
time: 13ms
memory: 11520kb

input:

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

output:

0
0
1
2
2
2
3
5
5
5
6
9
9
13
13
13
14
19
19
25
25
32
32
32
33
41
41
41
42
51
51
51
52
62
62
73
73
85
85
98
98
98
99
113
113
128
128
128
129
145
145
162
162
162
163
181
181
181
182
201
201
221
221
221
222
243
243
243
244
266
266
289
289
289
290
314
314
314
315
340
340
340
341
367
367
394
394
394
395
...

result:

ok 199998 numbers

Test #56:

score: 0
Accepted
time: 13ms
memory: 11188kb

input:

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

output:

0
0
0
1
2
2
4
4
7
7
7
8
12
12
12
13
18
18
24
24
31
31
39
39
39
40
49
49
59
59
59
60
71
71
71
72
84
84
84
85
98
98
112
112
127
127
143
143
143
144
161
161
179
179
198
198
198
199
219
219
240
240
240
241
263
263
263
264
287
287
287
288
312
312
337
337
337
338
364
364
391
391
391
392
420
420
449
449
47...

result:

ok 199997 numbers

Test #57:

score: 0
Accepted
time: 19ms
memory: 7364kb

input:

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

output:

0
1
1
1
2
4
4
7
7
7
8
12
12
12
13
18
18
24
24
31
31
39
39
48
48
48
49
59
59
59
60
71
71
71
72
84
84
97
97
97
98
112
112
112
113
128
128
128
129
145
145
162
162
180
180
180
181
200
200
200
201
221
221
221
222
243
243
243
244
266
266
289
289
313
313
338
338
364
364
364
365
392
392
392
393
421
421
421
...

result:

ok 199999 numbers