QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#406288#1163. Another Tree Queries ProblemDoqeTL 186ms9844kbC++233.3kb2024-05-07 08:57:062024-05-07 08:57:06

Judging History

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

  • [2024-05-07 08:57:06]
  • 评测
  • 测评结果:TL
  • 用时:186ms
  • 内存:9844kb
  • [2024-05-07 08:57:06]
  • 提交

answer

//try
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>to[N];
int dfn[N],dep[N],sz[N],top[N],son[N],fa[N],tt;
void dfs(int u,int f)
{
	if(f)to[u].erase(find(to[u].begin(),to[u].end(),f));
	dep[u]=dep[fa[u]=f]+1;
	sz[u]=1;
	for(int v:to[u])if(v!=f)
	{
		dfs(v,u);sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
}
void dfs1(int u,int f)
{
	top[u]=f;dfn[u]=++tt;if(son[u])dfs1(son[u],f);
	for(int v:to[u])if(v!=fa[u]&&v!=son[u])dfs1(v,v);
}
struct tag
{
	long long t;void TG(const tag&a){t+=a.t;}
	bool any()const{return t;}
	void clr(){t=0;}
}tg[N<<2];
struct node
{
	long long s;int len;
	void TG(const tag&a){s+=a.t*len;}
	node operator+(const node&a)const{return {s+a.s,len+a.len};}
}tr[N<<2];
inline void TG(int p,const tag&v){tr[p].TG(v),tg[p].TG(v);}
void PD(int p){if(tg[p].any())TG(p<<1,tg[p]),TG(p<<1|1,tg[p]),tg[p].clr();}
void build(int p,int l,int r){tr[p].len=r-l+1;if(l==r)return;int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);}
void mdf(int p,int l,int r,int L,int R,const tag&v)
{
	if(L>R)return;
	if(L<=l&&r<=R)return TG(p,v);
	int mid=l+r>>1;PD(p);
	if(L<=mid)mdf(p<<1,l,mid,L,R,v);
	if(R> mid)mdf(p<<1|1,mid+1,r,L,R,v);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}
node qry(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)return tr[p];
	int mid=l+r>>1;PD(p);
	if(R<=mid)return qry(p<<1,l,mid,L,R);
	if(L> mid)return qry(p<<1|1,mid+1,r,L,R);
	return qry(p<<1,l,mid,L,R)+qry(p<<1|1,mid+1,r,L,R);
}
inline int LCA(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
long long rsu[N];
long long dep_val;//\sum dep[i]*A_i
int main()
{
	int n;cin>>n;
	for(int i=1,u,v;i<n;++i)
		cin>>u>>v,to[u].push_back(v),to[v].push_back(u);
	dfs(1,0);dfs1(1,1);
	for(int i=1;i<=n;++i)sort(to[i].begin(),to[i].end(),[=](int x,int y){return dfn[x]<dfn[y];});
	build(1,1,n);
	for(int i=1;i<=n;++i)rsu[dfn[i]]=dep[i];
	for(int i=1;i<=n;++i)rsu[i]+=rsu[i-1];
	int q;cin>>q;
	while(q--)
	{
		int o,u,v;cin>>o>>u;
		if(o==1)
		{
			cin>>v;
			if(u==v)
			{
				mdf(1,1,n,1,n,{1});
				dep_val+=rsu[n];
			}
			else if(dfn[u]<dfn[v]||dfn[u]>=dfn[v]+sz[v])
			{
//				cerr<<"CASE2\n";
				mdf(1,1,n,dfn[v],dfn[v]+sz[v]-1,{1});
				dep_val+=rsu[dfn[v]+sz[v]-1]-rsu[dfn[v]-1];
			}
			else
			{
//				cerr<<"CASE3\n";
				int w=*--upper_bound(to[v].begin(),to[v].end(),u,[=](int x,int y){return dfn[x]<dfn[y];});
//				cerr<<u<<"->"<<v<<" "<<w<<endl;
				mdf(1,1,n,1,dfn[w]-1,{1});mdf(1,1,n,dfn[w]+sz[w],n,{1});
				dep_val+=rsu[dfn[w]-1]+(rsu[n]-rsu[dfn[w]+sz[w]-1]);
			}
		}
		else if(o==2)
		{
			cin>>v;
			dep_val+=dep[u]*(dep[u]+1ll)/2;
			dep_val+=dep[v]*(dep[v]+1ll)/2;
			while(top[u]!=top[v])
			{
				if(dep[top[u]]<dep[top[v]])swap(u,v);
				mdf(1,1,n,dfn[top[u]],dfn[u],{1}),u=fa[top[u]];
			}
			if(dfn[u]>dfn[v])swap(u,v);
			mdf(1,1,n,dfn[u],dfn[v],{1});
			dep_val-=dep[u]*(dep[u]+1ll)/2;
			dep_val-=dep[u]*(dep[u]-1ll)/2;
		}
		else
		{
			long long x1=dep[u]*qry(1,1,n,1,n).s,x2=dep_val,x3=0;
			int v=u;
			while(v)x3+=qry(1,1,n,dfn[v],dfn[v]+sz[v]-1).s,v=fa[v];
//			cerr<<x1<<","<<x2<<","<<x3<<endl;
			cout<<x1+x2-x3-x3<<endl;
		}
//			for(int i=1;i<=n;++i)cerr<<qry(1,1,n,dfn[i],dfn[i]).s<<",";cerr<<endl;
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 9764kb

input:

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

output:

1
5

result:

ok 2 number(s): "1 5"

Test #2:

score: 0
Accepted
time: 134ms
memory: 7808kb

input:

200
171 114
50 183
28 68
67 152
139 125
67 55
50 98
106 71
46 42
157 165
42 49
113 12
81 145
105 13
38 96
34 156
24 17
21 191
135 54
174 116
177 157
123 71
95 130
135 193
150 129
25 190
96 93
188 173
90 160
86 187
20 132
199 75
59 195
189 24
40 68
163 83
25 13
73 33
59 50
154 19
146 21
151 67
89 69
...

output:

826
908
813
1785
2288
1320
3038
2403
4809
3933
4123
3791
5819
4597
6632
7523
4562
8021
7393
9809
7647
6024
11272
7024
12979
14995
9349
9115
8437
11003
18272
22174
16139
17660
11063
14291
12045
18630
12368
17355
23696
20714
24792
20021
13962
22060
13163
19488
13321
25000
19336
30022
19846
33622
17483...

result:

ok 66664 numbers

Test #3:

score: 0
Accepted
time: 151ms
memory: 9788kb

input:

200
74 111
185 20
147 73
164 114
134 53
124 158
48 129
181 137
91 184
196 1
16 121
15 32
28 152
69 39
80 20
94 28
115 110
128 169
74 78
62 83
38 198
13 120
39 153
173 184
191 76
83 183
62 160
87 48
102 152
171 56
114 101
24 148
79 37
107 176
37 166
110 43
118 154
51 183
19 76
161 35
156 188
38 2
185...

output:

1370
1125
2073
1455
2146
3949
3644
4103
3588
6144
6509
6193
7897
6295
4892
7662
8945
5719
9379
7083
9801
9738
8849
9830
10280
6746
7187
9233
10055
7137
9998
11663
10971
10671
8110
12289
8053
11129
13414
13058
9407
14666
13973
16648
11946
10493
16924
10366
15002
13870
16504
13739
11619
17505
17472
15...

result:

ok 66525 numbers

Test #4:

score: 0
Accepted
time: 153ms
memory: 7720kb

input:

200
23 163
145 103
10 126
64 115
187 149
121 174
175 96
100 122
43 131
70 146
92 82
128 55
163 38
52 64
198 171
31 55
7 146
59 56
32 169
87 141
67 184
105 83
166 29
38 60
73 3
142 96
51 90
77 6
64 65
190 43
127 47
8 49
25 149
54 183
80 139
194 73
20 10
162 137
32 194
7 177
177 102
176 100
26 156
189...

output:

0
579
773
675
955
2161
990
1371
1374
2851
2885
5459
2470
3376
3567
5048
4887
7478
4269
4491
4832
5873
7244
5194
7547
7135
5420
9342
6996
6454
7018
6598
8680
8384
10668
10044
17203
9083
9130
14232
19537
8474
8993
8149
8895
9261
13980
7907
13129
14444
17109
18932
12344
16995
11807
17314
17988
16845
18...

result:

ok 66711 numbers

Test #5:

score: 0
Accepted
time: 170ms
memory: 5704kb

input:

200
154 157
99 156
198 117
32 10
103 146
128 180
147 97
171 77
176 15
50 164
177 200
32 112
167 17
51 137
109 16
30 19
124 148
69 9
17 132
118 71
86 167
144 181
41 26
192 93
12 192
50 160
129 55
61 137
114 100
176 34
193 56
153 7
114 192
16 179
72 134
33 144
186 32
128 129
101 150
164 110
122 174
76...

output:

634
3931
2152
7113
7375
5157
9559
12817
10446
13833
15305
40797
23884
24645
22737
53736
20362
23333
28618
35623
32028
30265
39761
49325
29804
29080
29011
49751
45649
44339
62237
53822
38820
45766
44653
54818
38658
75212
50663
60765
51069
42298
54510
52998
52624
66923
41027
42071
72369
69473
63263
75...

result:

ok 66422 numbers

Test #6:

score: 0
Accepted
time: 149ms
memory: 7724kb

input:

200
120 102
59 23
53 79
195 109
46 117
95 121
140 13
27 85
19 122
111 191
184 132
111 149
39 190
33 43
73 157
145 170
112 184
188 152
136 36
185 9
22 160
159 167
98 120
84 107
87 188
127 10
11 1
84 163
175 48
107 43
190 134
65 63
100 89
154 111
20 172
169 100
123 68
145 168
30 64
192 136
138 4
174 1...

output:

401
1241
192
1918
5911
5446
5207
6134
7211
5294
5854
9082
6605
7853
7443
8737
7711
8385
7847
20205
12335
14017
11619
14610
14134
13745
11750
10670
16602
13723
18149
27499
17623
18976
19490
24422
21994
21956
21988
25222
27276
27771
26231
30718
24090
27076
34656
28844
34483
42338
36386
56508
41942
262...

result:

ok 66545 numbers

Test #7:

score: 0
Accepted
time: 167ms
memory: 7784kb

input:

200
138 197
188 116
63 91
195 25
45 2
167 39
42 171
198 49
152 96
160 179
197 177
132 148
195 147
99 62
112 141
172 157
130 83
169 72
112 53
140 161
67 102
68 19
50 155
101 100
29 148
111 136
46 47
95 98
164 18
87 189
94 16
188 57
143 42
79 9
8 173
147 80
68 181
169 35
142 173
97 103
59 79
7 12
14 6...

output:

636
712
2555
7373
7031
6047
6328
7272
6621
8388
12218
9316
11050
9362
16764
12304
11310
8770
10640
12179
18497
9304
12958
13376
19046
10539
17210
11507
20492
10768
13003
26073
17084
23631
19020
17418
16943
22564
12617
29386
23968
12909
13798
26143
26989
19289
25718
29231
18093
24340
34059
14630
2751...

result:

ok 66906 numbers

Test #8:

score: 0
Accepted
time: 143ms
memory: 7788kb

input:

200
124 200
175 9
192 124
44 59
35 85
102 135
41 13
192 135
47 127
194 27
79 74
79 147
55 109
164 115
117 21
163 166
138 91
18 176
1 186
152 134
129 124
145 76
64 3
65 70
29 39
43 104
9 5
196 82
69 193
80 121
13 97
22 5
114 151
37 17
122 1
82 172
45 156
132 99
116 114
40 166
186 170
56 89
185 64
192...

output:

1383
832
867
3707
3037
6029
3393
5365
9813
4540
9746
11459
8006
6646
6288
12311
13084
12479
8263
10122
9999
17135
13629
9385
11820
12391
11734
12578
12416
17188
19992
18372
16027
16836
11411
10968
9559
20624
17440
19390
13532
12336
16824
22382
24643
20879
19771
13910
22414
27734
29026
34679
26670
35...

result:

ok 66845 numbers

Test #9:

score: 0
Accepted
time: 148ms
memory: 7740kb

input:

200
132 197
200 91
27 157
134 48
188 17
90 192
156 122
87 74
126 59
147 70
78 73
150 63
14 128
185 84
153 141
1 13
62 55
136 17
147 118
143 183
91 12
156 183
174 6
25 70
153 65
31 188
81 184
162 141
139 151
127 55
39 176
66 97
71 29
15 140
91 109
19 158
4 139
9 198
41 171
29 151
193 181
107 130
93 5...

output:

284
530
646
1628
1009
2075
2635
1378
2240
3464
3218
2807
1859
2945
6999
8613
7358
13815
10457
15287
12918
12103
11722
16018
8350
9665
10783
17172
11660
8056
13375
14673
15019
16969
16255
20244
22499
23795
20776
23450
16077
13131
28451
20641
20355
26305
22688
18969
24861
16021
19732
19226
19796
14033...

result:

ok 66707 numbers

Test #10:

score: 0
Accepted
time: 186ms
memory: 9844kb

input:

200
154 121
170 143
149 5
192 16
13 153
130 193
67 116
117 126
103 106
110 132
5 151
162 151
158 139
75 130
14 73
180 140
164 45
6 11
97 49
19 42
91 198
191 101
13 25
200 196
36 8
183 41
128 185
188 21
104 163
3 130
71 178
39 167
136 30
195 41
79 50
49 155
130 78
45 31
169 142
128 141
104 186
182 18...

output:

0
576
417
1087
2760
2009
2702
3600
3110
2626
2708
3349
3393
2679
2771
4275
3932
5209
10496
10178
9408
5955
10486
8002
10530
9384
10564
10138
13471
9277
8499
10907
9367
9793
8914
12280
8698
10524
7504
13317
9678
15462
6651
15042
8234
10403
16274
19062
24908
18621
26081
32920
24437
17339
23241
15559
1...

result:

ok 66701 numbers

Test #11:

score: 0
Accepted
time: 174ms
memory: 9692kb

input:

200
12 37
1 109
4 38
40 117
88 41
79 126
93 32
179 134
136 38
100 110
159 50
15 30
138 192
36 33
123 40
48 15
110 179
152 136
18 67
148 198
6 19
42 154
123 84
122 113
84 97
66 13
103 51
11 38
147 167
112 34
93 40
124 166
62 182
199 193
110 47
141 74
130 95
74 99
61 49
100 85
76 31
170 53
160 161
17 ...

output:

1179
1857
1287
1461
2138
2571
2154
5160
3474
4152
7278
8891
7923
10919
6637
12656
11975
8638
6696
15065
9881
15769
12433
18391
15323
20549
15701
24653
14407
26957
15718
15013
21985
17950
17135
26946
31389
28850
17187
34266
29522
36071
25311
28567
21469
40951
27260
28126
24227
22636
32422
32435
45958...

result:

ok 66474 numbers

Test #12:

score: 0
Accepted
time: 157ms
memory: 9844kb

input:

200
152 79
178 99
22 148
34 38
160 119
151 167
59 78
95 86
156 83
79 131
13 117
33 166
48 60
66 98
182 82
195 192
72 118
96 144
170 57
124 14
93 73
108 127
84 58
41 159
130 9
84 136
63 17
174 154
34 92
94 66
38 194
20 139
13 24
175 77
18 146
93 147
200 104
105 162
97 69
63 159
174 55
88 1
120 109
11...

output:

117
276
301
409
2822
4338
7065
11697
11844
13496
10284
12454
14877
14891
7128
9870
16086
15610
10516
9452
18068
21804
17293
19691
17098
34873
28102
19644
27534
40907
38340
24086
39217
28781
51000
43256
31846
55265
34176
51826
47579
47770
48582
29844
42842
48746
67970
63499
49647
78461
36927
34999
44...

result:

ok 66846 numbers

Test #13:

score: 0
Accepted
time: 150ms
memory: 9724kb

input:

200
29 83
5 60
74 152
70 105
13 34
117 189
70 56
112 133
114 69
186 71
147 18
188 168
104 69
109 164
33 85
100 5
63 55
86 39
22 103
27 90
18 164
68 109
152 62
96 95
102 47
3 136
19 180
120 166
89 10
101 73
110 12
51 28
54 154
14 53
69 198
169 113
15 66
133 177
119 81
17 158
186 182
179 125
43 6
123 ...

output:

147
182
355
3430
3264
4484
4258
5183
10476
5597
6840
11828
8671
9209
7813
7453
9345
17004
8002
16236
12280
9069
8761
15349
7311
16107
7939
10703
14069
10913
17148
15208
12891
17605
9751
22468
11330
9972
19989
16097
12753
12092
7676
16312
23916
17580
17598
11656
15244
17137
19720
17440
18772
21928
20...

result:

ok 66841 numbers

Test #14:

score: 0
Accepted
time: 145ms
memory: 7728kb

input:

200
5 83
168 5
146 74
195 66
108 154
79 192
60 44
129 15
16 34
58 103
148 72
24 94
198 86
53 90
49 54
85 33
30 152
24 171
77 188
60 149
88 68
121 172
183 4
156 48
166 39
50 125
85 30
150 51
160 173
135 71
29 18
163 51
168 117
95 99
73 18
157 52
93 62
166 177
10 81
95 55
96 107
122 47
129 125
151 2
1...

output:

0
582
447
420
1146
1322
699
1161
1361
751
5537
8319
5069
7567
5838
6444
9062
8849
8403
7307
9872
12400
11826
14798
11318
12876
11817
12497
13437
7424
8360
15989
14242
11619
12686
7932
11840
13568
12734
18357
11700
17337
13117
16039
19972
12074
12374
19366
10190
15961
13617
13457
25340
17296
15234
18...

result:

ok 66742 numbers

Test #15:

score: 0
Accepted
time: 132ms
memory: 7684kb

input:

200
165 28
88 38
198 54
185 176
55 65
3 70
33 17
119 83
64 183
51 182
110 132
163 30
44 184
27 98
172 152
108 126
159 141
193 57
185 30
46 135
28 172
82 190
167 96
182 58
90 164
75 107
63 10
49 122
24 188
122 18
7 199
95 171
116 117
103 37
109 62
16 85
2 16
193 73
180 141
37 139
41 138
91 82
55 187
...

output:

0
3660
3795
3881
4716
4909
8031
6885
5825
9403
8915
8907
15730
16134
12694
9468
9793
11279
16828
12589
17378
12412
14486
12786
12514
12192
11940
12227
19490
12599
13438
18871
21165
13627
19323
18553
23507
14575
15865
15903
26741
17836
12514
24305
18810
29307
18203
22006
26327
24535
18273
19722
21853...

result:

ok 66361 numbers

Test #16:

score: 0
Accepted
time: 76ms
memory: 7632kb

input:

200
1 190
90 167
130 77
109 15
142 188
125 173
186 10
49 4
135 80
177 133
126 190
190 184
177 161
185 81
176 199
121 143
178 154
197 100
112 108
69 63
32 193
28 141
38 170
78 141
96 110
103 185
169 154
85 127
149 65
200 19
142 140
159 183
192 110
198 180
200 133
23 102
18 50
124 170
182 145
75 138
1...

output:

1026
813
909
1013
1034
998
912
2500
2166
1637
2029
1885
1419
1953
1309
1149
1560
1947
2845
3550
2768
3756
4447
5490
3639
5220
6816
6578
4330
4267
7075
3285
4279
4712
8015
4583
7270
7391
10682
10048
11851
10943
15852
9980
7612
10542
10029
15003
8325
15540
19134
14752
12032
16157
11139
16167
18921
208...

result:

ok 66900 numbers

Test #17:

score: 0
Accepted
time: 157ms
memory: 7648kb

input:

200
110 156
141 180
172 107
50 116
155 161
96 121
169 116
130 113
72 37
40 36
57 188
182 150
5 14
28 36
105 15
21 88
86 146
8 24
183 21
165 41
175 16
176 189
195 20
62 89
114 19
84 134
77 85
143 155
164 145
29 85
129 65
186 195
127 184
86 94
121 58
194 94
113 11
3 95
78 127
174 53
142 194
33 153
118...

output:

899
2180
5034
4538
4479
4060
4032
6359
8094
7582
12192
7197
10723
10710
11295
17192
10176
14534
15884
13725
17130
13985
16751
11450
17115
14891
13434
12863
18140
21221
18824
17271
21536
26527
15263
15363
21599
15711
26876
19087
21824
32002
39877
32659
44874
34519
44881
26958
53759
29046
26022
34644
...

result:

ok 67133 numbers

Test #18:

score: 0
Accepted
time: 125ms
memory: 7744kb

input:

200
68 75
63 3
86 97
159 95
81 11
172 71
111 83
37 60
138 77
65 28
2 89
120 73
191 88
186 160
63 182
35 177
187 81
10 192
137 104
168 64
153 92
126 89
76 2
32 127
179 199
147 110
29 181
123 108
114 185
184 165
196 185
176 73
20 157
151 117
79 60
105 171
9 135
23 126
47 21
16 71
57 102
98 190
200 5
1...

output:

23
56
362
268
1026
1336
722
1743
1138
1308
1385
2276
1149
2030
1512
1813
4023
3115
1415
4023
3636
2292
2511
1954
2286
4941
4440
5778
8655
9550
7477
8415
8322
15688
11005
12933
20059
23932
13732
11774
15204
15757
17501
15771
16305
24777
26776
11150
21141
15635
18321
23128
18684
23743
14917
28901
2050...

result:

ok 66784 numbers

Test #19:

score: 0
Accepted
time: 138ms
memory: 9760kb

input:

200
49 182
69 90
14 171
47 79
147 96
61 134
104 124
84 17
145 103
17 139
181 183
36 61
97 132
134 89
195 188
149 75
140 115
117 22
119 105
153 8
64 155
125 173
24 149
14 56
24 30
86 71
44 87
53 5
57 109
183 191
7 105
193 95
59 131
16 35
179 89
177 131
106 170
187 123
111 31
66 192
20 84
136 180
195 ...

output:

0
0
259
11224
10848
7898
7684
5134
8323
6748
10133
12200
7279
12945
10348
12081
10411
11616
9907
10458
13802
23642
21059
17299
22202
18729
11794
18257
22724
22534
19187
22860
25997
31707
18627
18017
28852
18592
41135
37947
37175
28741
40698
28146
42828
35785
40529
42822
28812
37048
42644
38102
29170...

result:

ok 66513 numbers

Test #20:

score: 0
Accepted
time: 130ms
memory: 5644kb

input:

200
185 99
9 97
47 122
154 157
177 17
150 52
98 94
74 139
182 186
180 45
56 72
86 170
59 13
120 102
189 121
200 165
28 105
157 137
99 116
26 173
123 131
159 167
49 69
149 61
41 117
143 66
125 176
110 65
103 127
23 97
170 84
112 136
146 89
30 103
29 55
190 148
114 1
5 112
14 40
8 199
163 45
17 147
16...

output:

195
171
2532
2081
2421
1663
3163
2855
4667
2782
2949
4211
2988
4680
6878
8881
6240
5906
8911
8514
5666
7079
10423
11583
7661
11458
9997
18063
14597
14815
12675
16339
15930
13964
14258
15199
14784
15161
19007
21343
14645
14608
20454
23194
12330
18345
17302
22665
26968
18589
19990
21313
30611
22333
27...

result:

ok 66284 numbers

Test #21:

score: 0
Accepted
time: 173ms
memory: 9728kb

input:

200
30 51
123 16
30 24
100 88
78 13
10 113
189 92
35 145
118 91
136 110
105 39
126 65
188 72
123 36
64 34
200 43
102 166
131 72
97 32
137 104
156 19
132 119
31 115
122 69
44 113
3 101
150 14
27 133
94 168
185 138
76 2
161 52
80 65
128 100
94 124
95 187
181 15
121 127
128 13
120 6
119 48
61 154
77 48...

output:

0
0
234
1541
2203
1423
5234
6516
5633
3736
6939
7056
6087
6436
9941
4660
9789
6450
6730
9026
5765
5866
11968
10649
16523
12195
13649
11583
17974
17878
14088
17791
18871
16531
17592
14081
15669
21209
15071
19145
21733
24785
14067
14136
26564
22124
16612
19281
18879
14506
19834
16179
25259
23170
15314...

result:

ok 66722 numbers

Test #22:

score: -100
Time Limit Exceeded

input:

200000
140678 114065
114396 56342
64808 85352
82277 129643
137097 165679
102009 137295
168344 95029
29170 86751
87771 135959
125510 54610
102696 170877
55331 37358
81454 197045
61683 168840
35500 3346
110470 9436
117496 80955
120054 91200
31050 64180
190832 27883
151667 154880
95009 98309
160458 587...

output:

0
0
44741
379880
1817768
2222612
2872777
3288760
2945542
3089457
4002074
3555568
5188409
4337839
6903857
4845585
7154069
6513556
7768362
6806248
8211776
7363480
7718426
7862425
9876289
10522535
7425031
9119937
7528296
8198347
8826858
11896364
8733250
14265289
11495063
8993693
9348650
13555155
109138...

result: