QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#801302#9845. Reverse LISrotcar07AC ✓116ms63120kbC++232.0kb2024-12-06 21:06:302024-12-06 21:06:30

Judging History

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

  • [2024-12-06 21:06:30]
  • 评测
  • 测评结果:AC
  • 用时:116ms
  • 内存:63120kb
  • [2024-12-06 21:06:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=2e5+5;
int n,a[maxn];
typedef long long ll;
struct node{
	pair<ll,int> mn,mx;
	tuple<ll,int,int> ans,fans;
	ll sum;
	node(int x=0,int pos=0):sum(x),mn(x,pos),mx(x,pos),ans(0,pos,pos),fans(0,pos,pos){}
	node(auto a,auto b,auto c,auto d,ll sum):mn(a),mx(b),ans(c),sum(sum),fans(d){}
	inline void add(ll x){mn.first+=x,mx.first+=x,sum+=x;}
	inline node operator + (node w)const{
		w.add(sum);
		return node(min(mn,w.mn),max(mx,w.mx),max({ans,w.ans,{w.mx.first-mn.first,mn.second,w.mx.second}}),max({fans,w.fans,{mx.first-w.mn.first,mx.second,w.mn.second}}),w.sum);
	}
	inline void flip(){swap(mn,mx);mn.first=-mn.first;mx.first=-mx.first;sum=-sum;swap(ans,fans);}
}t[maxn<<2];
#define ls p<<1
#define rs p<<1|1
bool g[maxn<<2];
inline void upd(int p){t[p].flip();g[p]^=1;}
inline void pushdown(int p){if(g[p])upd(ls),upd(rs),g[p]=0;}
void build(int p,int l,int r){
	if(l==r) return t[p]=node(a[l],l),void();
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	t[p]=t[ls]+t[rs];
}
void modify(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return upd(p);
	int mid=l+r>>1;pushdown(p);
	if(ql<=mid)modify(ls,l,mid,ql,qr);
	if(qr>mid) modify(rs,mid+1,r,ql,qr);
	t[p]=t[ls]+t[rs];
	// cout<<l<<' '<<r<<" "<<t[p].mn.first<<' '<<t[p].mx.first<<' '<<get<0>(t[p].ans)<<' '<<get<0>(t[p].fans)<<' '<<t[p].sum<<'\n';
}
ll ans[maxn];
int main(){
	std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	char c;
	cin>>n;ll sum=0;
	for(int i=1,x;i<=n;i++) cin>>c>>x,a[i]=(c=='1'?-x:x),sum+=(c-'0')*x;
	build(1,1,n);
	const auto x=t[1].mx;
	if(x.first<0){
		ans[0]=sum;
	}else{
		ans[0]=x.first+sum;modify(1,1,n,1,x.second);
	}
	for(int i=1;i<=n;i++){
		auto [a,b,c]=t[1].ans;
		const auto [d,e]=t[1].mx;
		if(d>a) a=d,b=0,c=e;
		if(a<0){ans[i]=ans[i-1];continue;}
		ans[i]=ans[i-1]+a;
		if(b<c)modify(1,1,n,b+1,c);
	}
	int q;cin>>q;
	while(q--){
		int k;cin>>k;
		cout<<ans[k]<<'\n';
	}
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 61088kb

input:

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

output:

8
10

result:

ok 2 lines

Test #2:

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

input:

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

output:

16
12
16

result:

ok 3 lines

Test #3:

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

input:

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

output:

26
35

result:

ok 2 lines

Test #4:

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

input:

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

output:

21
22
22
20
18
22
22
22
22

result:

ok 9 lines

Test #5:

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

input:

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

output:

60
60
55
38
60
60
59
47
60
60

result:

ok 10 lines

Test #6:

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

input:

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

output:

60
53
56
60
60
59
60
36
60
60
45

result:

ok 11 lines

Test #7:

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

input:

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

output:

57
57
44
57
57
56
57
37
57
53
49
57

result:

ok 12 lines

Test #8:

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

input:

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

output:

79
72
79
48
59
79
67
79
79
79
77
79
79

result:

ok 13 lines

Test #9:

score: 0
Accepted
time: 109ms
memory: 63064kb

input:

200000
0 436556279
1 565705658
0 668870945
1 240708279
0 739103024
1 152486119
0 990923394
1 58158598
0 655333287
1 608908312
0 790518819
1 772943312
0 364750193
1 102925110
0 356251209
1 360492163
0 16077861
1 188892495
0 593145089
1 120711149
0 451468643
1 845714197
0 78062746
1 389517252
0 505063...

output:

77040100163082
100051293706350
100051293706350
100051293706350
87860793940635
100051293706350
100051293706350
100051293706350
100051293706350
99875892278811
100051293706350
100051293706350
75021589641602
56691347880111
100051293706350
100051293706350
100051293706350
100051293706350
100051293706350
8...

result:

ok 200000 lines

Test #10:

score: 0
Accepted
time: 101ms
memory: 63120kb

input:

200000
1 363074084
0 294832612
1 444054980
0 835710168
1 249169496
0 805875497
1 29528291
0 951479506
1 14770179
0 325671780
1 605441910
0 891539756
1 307608545
0 316173460
1 8457932
0 328018377
1 367809265
0 416682142
1 824380597
0 815472303
1 789543670
0 654071241
1 995061255
0 992973961
1 4419033...

output:

99991304177162
99991304177162
94059593700365
97385597866379
99991304177162
85968624213847
89234988260896
78536575599315
66768120086366
99991304177162
99991304177162
99968432585267
95872775791316
77725218828132
99991304177162
99991304177162
99991304177162
99991304177162
96485539616545
98675617652670
...

result:

ok 200000 lines

Test #11:

score: 0
Accepted
time: 102ms
memory: 63052kb

input:

200000
0 544408663
1 791727648
0 980501409
1 370185937
0 422867780
1 513854792
0 42174059
1 162393361
0 133600184
1 687082529
0 458929528
1 443727403
0 825200920
1 330305842
0 852328406
1 607592799
0 867595963
1 565557267
0 454353351
1 682661952
0 445125230
1 457970164
0 106521923
1 367134518
0 5390...

output:

77857332764809
100177577552209
100177577552209
89792971537403
70660565284685
100177577552209
87750065208350
69940832809172
100177577552209
100177577552209
89245436167584
100177577552209
73008090311888
94785004833712
100177577552209
100177577552209
57025040832340
100177577552209
100177577552209
87358...

result:

ok 200000 lines

Test #12:

score: 0
Accepted
time: 104ms
memory: 63044kb

input:

200000
0 179411500
1 611625425
0 71129071
1 565609349
0 949046439
1 942569005
0 807727866
1 728992006
0 858990740
1 456834608
0 896618095
1 850245774
0 666913109
1 364320752
0 206442146
1 475190644
0 928908110
1 24307752
0 593283371
1 853840372
0 975040106
1 872882871
0 25254755
1 32612783
0 2116061...

output:

81077900844246
99910101291413
99910101291413
99910101291413
98776511058121
99910101291413
99910101291413
99910101291413
98699880171557
99910101291413
84888704180774
98164351679150
99910101291413
89083616710943
86745129653576
68936737241496
99910101291413
80304843622213
99910101291413
99910101291413
...

result:

ok 200000 lines

Test #13:

score: 0
Accepted
time: 110ms
memory: 62972kb

input:

199999
0 967458919
1 189222839
0 949057619
1 528034592
0 20832495
1 704012569
0 625887032
1 771645987
0 258696847
1 38689284
0 768577285
1 214808485
0 475043289
1 459686205
0 183482430
1 779812015
0 218271840
1 684002353
0 473215145
1 102693165
0 623979839
1 968092523
0 919086545
1 295194735
0 98827...

output:

95384005428844
56042956363272
89004026597948
100001212049075
100039414619134
100039414619134
91913806081166
69550390331708
100039414619134
100039414619134
96968978804562
99955432695085
100039414619134
100039414619134
100039414619134
100039414619134
99992577404867
92796491752773
96839065476861
752262...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 108ms
memory: 63020kb

input:

199999
1 192107066
0 5580750
1 159016081
0 982884693
1 997756837
0 778613497
1 160096136
0 278275624
1 999114977
0 428589074
1 805573723
0 207381937
1 649549888
0 189073929
1 682262112
0 749820593
1 503826487
0 281577617
1 154748750
0 438002924
1 669784545
0 810605216
1 131627457
0 642904492
1 44699...

output:

99952452671431
99478192540142
77679947127209
99952452671431
99952452671431
99952452671431
89170737405893
99952452671431
88967506927607
93846584318100
99107967024879
73329631313307
96442009584346
99952452671431
99951790862823
81810208297261
90972050265493
99756771860489
94091343529449
97343789632032
...

result:

ok 200000 lines

Test #15:

score: 0
Accepted
time: 107ms
memory: 63104kb

input:

199999
0 476585790
1 529410339
0 605269094
1 651692325
0 292403150
1 485998890
0 236534918
1 127526159
0 379485344
1 573213578
0 174106662
1 837279285
0 466138446
1 893222125
0 904771564
1 896251997
0 613388839
1 591916501
0 371588719
1 785340512
0 481248942
1 548314900
0 420619453
1 505548971
0 248...

output:

100026710004194
100026710004194
97553719835481
88279937159590
99813951891022
54055493315049
91871464059705
99747083886370
100026710004194
100026710004194
100026710004194
98450400811048
99495440045470
99023707080336
88516404441075
82448485473648
100026710004194
100026710004194
99830368837194
86780795...

result:

ok 200000 lines

Test #16:

score: 0
Accepted
time: 116ms
memory: 62904kb

input:

199999
0 122196536
1 142586073
0 881773229
1 456602175
0 837387986
1 63398255
0 486704474
1 728728820
0 735530318
1 221966336
0 455240701
1 39523197
0 385723953
1 800270945
0 441526435
1 856205126
0 664018864
1 65062713
0 954456139
1 389305297
0 997743157
1 31472771
0 289315180
1 629106484
0 1429086...

output:

94969047850650
98593021280221
100176533970179
69068793273925
100176533970179
100176533970179
90214376318926
100176533970179
91981530936444
100176533970179
78979723486654
100176533970179
98874513318793
96186068469928
98442135781931
100176533970179
100176533970179
100176533970179
100176533970179
71794...

result:

ok 200000 lines

Test #17:

score: 0
Accepted
time: 109ms
memory: 63040kb

input:

199999
1 290248097
0 273185326
1 650712312
0 608095947
1 109169561
0 33083800
1 147300420
0 360100508
1 709775461
0 650462256
1 399240821
0 588386822
1 339426463
0 844675691
1 809925543
0 475036112
1 41026567
0 931320966
1 97406298
0 941257416
1 477341693
0 35223294
1 718295795
0 850141248
1 1640837...

output:

99914736249825
99914736249825
95557740938498
99914736249825
99810436788740
81988951918000
99914736249825
84654589482020
69788383834104
99914736249825
99914736249825
96305006081797
98747266338145
99914736249825
99542928151865
98674871568842
99914736249825
99914736249825
99914736249825
99914736249825
...

result:

ok 200000 lines

Test #18:

score: 0
Accepted
time: 109ms
memory: 63112kb

input:

199999
1 404396972
0 779005827
1 751320679
0 206173187
1 800707141
0 369072185
1 127289327
0 502496433
1 874151965
0 25605602
1 612338983
0 928634859
1 676628444
0 846785406
1 449721746
0 585946652
1 747555198
0 998765442
1 763840325
0 53200482
1 88145106
0 514637398
1 186607466
0 395938065
1 189629...

output:

100003183109085
88834321235327
62597444721310
100003183109085
95242488962449
100003183109085
96905354566916
100003183109085
94975243243342
100003183109085
58069275495738
72742836225466
95791170763474
68330354577966
99996272370899
85810540316276
95154140622614
100003183109085
100003183109085
10000318...

result:

ok 200000 lines

Test #19:

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

input:

137
1 19
0 25
1 95
0 56
1 4
0 51
1 40
0 35
1 59
0 43
1 95
0 89
1 18
0 15
1 81
0 79
1 84
0 97
1 83
0 20
1 73
0 79
1 74
0 29
1 49
0 62
1 46
0 11
1 37
0 20
1 12
0 48
1 2
0 25
1 88
0 86
1 87
0 26
1 28
0 2
1 12
0 85
1 55
0 10
1 74
0 7
1 98
0 80
1 11
0 62
1 58
0 97
1 80
0 23
1 96
0 58
1 74
0 1
1 92
0 39
1...

output:

7185
7185
7185
7185
7111
7159
7185
7154
7185
7185
4269
7185
6911
7185
7185
7185
5620
7185
6348
7037
7185
6837
7185
7185
7185
4638
7131
4926
7185
7185
7164
5540
7180
5857
6808
7184
4831
5285
7185
7185
7185
7185
7185
7052
6531
7185
7185
7185
6773
6888
7140
5371
4439
6738
7121
7185
7185
7185
6934
7185
...

result:

ok 138 lines

Test #20:

score: 0
Accepted
time: 15ms
memory: 61788kb

input:

30287
1 87
0 15
1 42
0 63
1 91
0 25
1 80
0 15
1 11
0 18
1 58
0 68
1 48
0 11
1 91
0 5
1 2
0 24
1 89
0 41
1 10
0 4
1 50
0 94
1 92
0 87
1 52
0 94
1 83
0 2
1 9
0 45
1 40
0 51
1 12
0 80
1 90
0 14
1 18
0 38
1 91
0 29
1 42
0 81
1 78
0 65
1 69
0 53
1 20
0 94
1 14
0 98
1 19
0 15
1 23
0 93
1 73
0 28
1 63
0 23...

output:

1525879
1223740
1408659
1490280
1525879
1335055
1025719
1525879
1525879
1525879
1525879
898980
1474593
1525879
1499031
1518997
1525879
1525364
1522773
1523940
1525879
1525879
1525879
1471396
1525879
1343546
1525879
1525879
1525879
1330543
1525879
1432510
1293294
1525879
1349941
1500348
1467395
13069...

result:

ok 30288 lines

Test #21:

score: 0
Accepted
time: 60ms
memory: 62796kb

input:

130412
1 87
0 51
1 85
0 67
1 53
0 1
1 57
0 69
1 24
0 84
1 24
0 79
1 39
0 76
1 29
0 61
1 79
0 77
1 77
0 92
1 93
0 65
1 42
0 39
1 78
0 89
1 33
0 53
1 58
0 63
1 32
0 21
1 53
0 91
1 85
0 49
1 93
0 3
1 76
0 83
1 83
0 60
1 25
0 23
1 42
0 44
1 80
0 27
1 45
0 51
1 75
0 13
1 53
0 81
1 80
0 89
1 62
0 59
1 52
...

output:

6582280
6584440
6584440
5361937
5893789
6584440
6273148
6584440
4566577
5944186
5597477
6409554
6584440
5261185
6411624
4815450
4295361
5694655
6584440
6584440
6583613
6499431
6508635
5579457
6584440
6584440
6584440
6584440
6385559
6584440
6523848
6584440
6584440
6584440
6246801
6584440
6550575
6584...

result:

ok 130413 lines

Test #22:

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

input:

1086
1 80
0 58
1 77
0 91
1 16
0 91
1 65
0 6
1 57
0 53
1 69
0 88
1 61
0 5
1 17
0 30
1 71
0 73
1 3
0 58
1 65
0 84
1 34
0 8
1 93
0 11
1 6
0 70
1 42
0 84
1 21
0 27
1 53
0 46
1 73
0 53
1 18
0 26
1 75
0 32
1 99
0 81
1 26
0 81
1 36
0 35
1 98
0 83
1 78
0 6
1 38
0 77
1 7
0 85
1 62
0 81
1 23
0 33
1 69
0 3
1 3...

output:

55705
36606
47773
55705
50020
55705
54329
55705
55437
40837
55705
39998
55705
55705
55705
51355
55705
55705
55705
55705
49045
55705
42287
54202
55705
55705
54239
53825
55705
53888
55705
55297
55705
54995
34959
55594
55705
55705
52630
55705
54922
43877
55562
53326
55705
55705
41813
49503
49849
55705
...

result:

ok 1087 lines

Test #23:

score: 0
Accepted
time: 88ms
memory: 62984kb

input:

167358
1 79
0 45
1 5
0 23
1 68
0 79
1 77
0 98
1 5
0 64
1 62
0 22
1 20
0 98
1 41
0 67
1 8
0 58
1 79
0 32
1 32
0 30
1 9
0 22
1 81
0 27
1 37
0 51
1 56
0 4
1 36
0 40
1 22
0 89
1 71
0 24
1 22
0 20
1 4
0 26
1 91
0 39
1 11
0 51
1 19
0 4
1 38
0 29
1 72
0 13
1 72
0 46
1 83
0 90
1 39
0 43
1 81
0 21
1 27
0 65
...

output:

7181188
8479752
7116641
7149029
8469863
8370159
8479752
8458769
8479752
8479752
8479752
8479752
8479752
8452002
8479752
8479752
8406105
7160084
8479752
6244533
8479752
8479752
8479752
8479752
8479752
7227038
8479752
8303764
8189991
7509098
8479752
8377083
5050147
5496969
8428196
8479752
8479752
8479...

result:

ok 167359 lines

Test #24:

score: 0
Accepted
time: 41ms
memory: 61856kb

input:

97375
0 999905150
1 999921206
0 999925498
1 999956335
0 999952711
1 999990578
0 999992186
1 999911143
0 999937710
1 999908315
0 999901834
1 999966858
0 999915427
1 999985803
0 999968106
1 999990276
0 999905133
1 999923106
0 999935181
1 999905987
0 999945168
1 999920915
0 999927990
1 999906892
0 9999...

output:

77580869488508
87840028105307
93829472314309
97370124841952
96014259462291
90528783776414
97370124841952
90123821137641
95951265670248
97370124841952
97370124841952
51894977067446
58943887376185
50398926071214
97370124841952
97370124841952
90935746038418
97370124841952
59262877858507
86622135714967
...

result:

ok 97376 lines

Test #25:

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

input:

35645
0 999954453
1 999970865
0 999950128
1 999921782
0 999983379
1 999966667
0 999963874
1 999963886
0 999940249
1 999917186
0 999925366
1 999944296
0 999979224
1 999994265
0 999982952
1 999986042
0 999936120
1 999925060
0 999976504
1 999967980
0 999941243
1 999997055
0 999946044
1 999912566
0 9999...

output:

25404051148217
35643210896395
35643210896395
21967212961030
27356925413248
35643210896395
35643210896395
35643210896395
35643210896395
31709580860031
35643210896395
35643210896395
30970644705153
33566412143236
31289617395664
30391693316410
35643210896395
22641188323090
33234443097809
35643210896395
...

result:

ok 35646 lines

Test #26:

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

input:

14151
0 999960780
1 999941229
0 999950858
1 999947291
0 999980012
1 999984423
0 999998857
1 999958869
0 999937338
1 999964771
0 999900358
1 999965058
0 999938051
1 999953604
0 999915084
1 999979720
0 999931430
1 999937445
0 999992092
1 999921212
0 999909362
1 999982066
0 999999050
1 999990328
0 9999...

output:

14150286511160
8057701128421
11084554471963
13433356412044
14150286511160
14150286511160
8105700391636
14150286511160
12667426652169
9658644232895
14150286511160
11703507554115
14150286511160
14150286511160
7871703238569
14150286511160
14150286511160
7104670022173
8896678723779
14150286511160
105275...

result:

ok 14152 lines

Test #27:

score: 0
Accepted
time: 81ms
memory: 62952kb

input:

156534
1 999996799
0 999998446
1 999938877
0 999935210
1 999988422
0 999970704
1 999935532
0 999937079
1 999963561
0 999900573
1 999908284
0 999952931
1 999966961
0 999966875
1 999957059
0 999950990
1 999977562
0 999965436
1 999964949
0 999953577
1 999970669
0 999951263
1 999947085
0 999945442
1 999...

output:

156526167538866
125781895244039
89498733322035
156526167538866
94389625311890
156526167538866
156526167538866
156526167538866
80348627912335
156526167538866
155705249416087
122342149136230
85283769172413
156526167538866
156526167538866
121321222115679
82817745413105
156526167538866
125743898115256
1...

result:

ok 156535 lines

Test #28:

score: 0
Accepted
time: 11ms
memory: 61128kb

input:

16427
0 999960253
1 999958017
0 999958203
1 999927981
0 999914577
1 999963311
0 999941691
1 999967317
0 999927228
1 999911086
0 999941139
1 999999387
0 999949647
1 999984946
0 999918367
1 999941866
0 999960667
1 999940011
0 999998081
1 999919075
0 999944652
1 999956853
0 999988831
1 999950054
0 9999...

output:

10820607556466
13803412145929
12513509265661
16426172598527
16426172598527
16426172598527
16426172598527
10707612688388
15936220869209
15355276215087
10186633370976
16426172598527
14627342292842
16426172598527
16426172598527
8948657978410
15459266462274
12822487571947
13219458149053
13049470932670
1...

result:

ok 16428 lines

Test #29:

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

input:

1
1 1
1
1

output:

1

result:

ok single line: '1'

Test #30:

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

input:

1
0 1
1
0

output:

1

result:

ok single line: '1'

Test #31:

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

input:

1
0 1
1
1

output:

1

result:

ok single line: '1'

Test #32:

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

input:

1
1 1
1
0

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 73ms
memory: 63048kb

input:

200000
0 5000
1 10000
0 15000
1 20000
0 25000
1 30000
0 35000
1 40000
0 45000
1 50000
0 55000
1 60000
0 65000
1 70000
0 75000
1 80000
0 85000
1 90000
0 95000
1 100000
0 105000
1 110000
0 115000
1 120000
0 125000
1 130000
0 135000
1 140000
0 145000
1 150000
0 155000
1 160000
0 165000
1 170000
0 17500...

output:

100000500000000
100000500000000
100000500000000
78468937470000
70569557190000
88308744540000
100000500000000
97837611990000
100000500000000
99622441400000
97888679240000
74050611390000
99629365800000
100000500000000
73763818590000
100000500000000
100000500000000
100000500000000
98183224200000
100000...

result:

ok 200000 lines

Test #34:

score: 0
Accepted
time: 80ms
memory: 62932kb

input:

200000
1 1000000000
0 999995000
1 999990000
0 999985000
1 999980000
0 999975000
1 999970000
0 999965000
1 999960000
0 999955000
1 999950000
0 999945000
1 999940000
0 999935000
1 999930000
0 999925000
1 999920000
0 999915000
1 999910000
0 999905000
1 999900000
0 999895000
1 999890000
0 999885000
1 99...

output:

100000500000000
100000500000000
80527331755000
98617881795000
57120217755000
100000500000000
100000500000000
62262434355000
100000500000000
99991427955000
78454169875000
79657231020000
90820744480000
97495730380000
84908482000000
70885945680000
98934553995000
96411711595000
100000500000000
100000500...

result:

ok 200000 lines

Test #35:

score: 0
Accepted
time: 74ms
memory: 62988kb

input:

200000
1 5000
0 10000
1 15000
0 20000
1 25000
0 30000
1 35000
0 40000
1 45000
0 50000
1 55000
0 60000
1 65000
0 70000
1 75000
0 80000
1 85000
0 90000
1 95000
0 100000
1 105000
0 110000
1 115000
0 120000
1 125000
0 130000
1 135000
0 140000
1 145000
0 150000
1 155000
0 160000
1 165000
0 170000
1 17500...

output:

93386979195000
100000500000000
100000500000000
100000500000000
67089304195000
100000500000000
100000500000000
100000500000000
100000500000000
84958435995000
65876787280000
95221504720000
100000500000000
99997162555000
100000500000000
82487362555000
100000500000000
100000500000000
100000500000000
712...

result:

ok 200000 lines

Test #36:

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

input:

200000
1 1000000000
0 10000
1 999990000
0 20000
1 999980000
0 30000
1 999970000
0 40000
1 999960000
0 50000
1 999950000
0 60000
1 999940000
0 70000
1 999930000
0 80000
1 999920000
0 90000
1 999910000
0 100000
1 999900000
0 110000
1 999890000
0 120000
1 999880000
0 130000
1 999870000
0 140000
1 99986...

output:

100001000000000
100001000000000
100001000000000
93477317780000
83924508800000
91200581100000
99892067000000
98938039000000
100001000000000
93992863680000
100001000000000
89486545240000
100001000000000
100001000000000
89851678360000
99966737990000
99249484390000
98834923980000
100001000000000
1000010...

result:

ok 200000 lines

Test #37:

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

input:

200000
0 5000
1 1000000000
0 15000
1 1000000000
0 25000
1 1000000000
0 35000
1 1000000000
0 45000
1 1000000000
0 55000
1 1000000000
0 65000
1 1000000000
0 75000
1 1000000000
0 85000
1 1000000000
0 95000
1 1000000000
0 105000
1 1000000000
0 115000
1 1000000000
0 125000
1 1000000000
0 135000
1 1000000...

output:

150000000000000
150000000000000
103301619185000
150000000000000
150000000000000
149934550385000
123384921600000
136438368005000
106927807025000
150000000000000
150000000000000
134603744600000
130020583160000
150000000000000
150000000000000
150000000000000
126090004485000
118058373360000
122895324360...

result:

ok 200000 lines

Test #38:

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

input:

200000
1 1
0 10000
1 1
0 20000
1 1
0 30000
1 1
0 40000
1 1
0 50000
1 1
0 60000
1 1
0 70000
1 1
0 80000
1 1
0 90000
1 1
0 100000
1 1
0 110000
1 1
0 120000
1 1
0 130000
1 1
0 140000
1 1
0 150000
1 1
0 160000
1 1
0 170000
1 1
0 180000
1 1
0 190000
1 1
0 200000
1 1
0 210000
1 1
0 220000
1 1
0 230000
1 1...

output:

50000500017242
50000500036927
50000500100000
50000500042369
50000500100000
50000500019295
50000500044467
50000500070408
50000500100000
50000500049608
50000500096662
50000500073753
50000500100000
50000500100000
50000500085613
50000500100000
50000500100000
50000500100000
50000500100000
50000500100000
...

result:

ok 200000 lines

Test #39:

score: 0
Accepted
time: 85ms
memory: 63052kb

input:

200000
1 5000
0 999995000
1 15000
0 999985000
1 25000
0 999975000
1 35000
0 999965000
1 45000
0 999955000
1 55000
0 999945000
1 65000
0 999935000
1 75000
0 999925000
1 85000
0 999915000
1 95000
0 999905000
1 105000
0 999895000
1 115000
0 999885000
1 125000
0 999875000
1 135000
0 999865000
1 145000
0...

output:

77752269435000
80388387750000
100000000000000
97949089590000
78731761935000
97867085795000
78472719935000
97994660790000
100000000000000
99706181795000
100000000000000
100000000000000
100000000000000
100000000000000
93304843750000
82197085575000
99594549435000
99909278560000
100000000000000
10000000...

result:

ok 200000 lines

Test #40:

score: 0
Accepted
time: 72ms
memory: 62700kb

input:

200000
1 1000000000
0 999995000
1 999990000
0 999985000
1 999980000
0 999975000
1 999970000
0 999965000
1 999960000
0 999955000
1 999950000
0 999945000
1 999940000
0 999935000
1 999930000
0 999925000
1 999920000
0 999915000
1 999910000
0 999905000
1 999900000
0 999895000
1 999890000
0 999885000
1 99...

output:

96745423875000
100000500000000
100000500000000
60238705120000
100000500000000
67318504480000
84244247520000
51035092000000
79271427280000
64457090155000
100000500000000
69655333920000
90759799500000
80580964795000
100000500000000
100000500000000
58279127955000
68117991955000
95628279795000
100000500...

result:

ok 200000 lines

Test #41:

score: 0
Accepted
time: 78ms
memory: 63112kb

input:

200000
0 1000000000
1 1000000000
0 999990000
1 1000000000
0 999980000
1 1000000000
0 999970000
1 1000000000
0 999960000
1 1000000000
0 999950000
1 1000000000
0 999940000
1 1000000000
0 999930000
1 1000000000
0 999920000
1 1000000000
0 999910000
1 1000000000
0 999900000
1 1000000000
0 999890000
1 100...

output:

150000500000000
150000500000000
150000500000000
131560746440000
150000500000000
126556714250000
150000500000000
150000500000000
133267676750000
150000500000000
115906108240000
150000500000000
150000500000000
150000500000000
149746564990000
105790885040000
144522615500000
150000500000000
138138397220...

result:

ok 200000 lines

Test #42:

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

input:

200000
0 1000000000
1 1
0 999990000
1 1
0 999980000
1 1
0 999970000
1 1
0 999960000
1 1
0 999950000
1 1
0 999940000
1 1
0 999930000
1 1
0 999920000
1 1
0 999910000
1 1
0 999900000
1 1
0 999890000
1 1
0 999880000
1 1
0 999870000
1 1
0 999860000
1 1
0 999850000
1 1
0 999840000
1 1
0 999830000
1 1
0 99...

output:

50000500066112
50000500011702
50000500069714
50000500043062
50000500083080
50000500054813
50000500100000
50000500087767
50000500025238
50000500100000
50000500100000
50000500015882
50000500100000
50000500100000
50000500100000
50000500001658
50000500100000
50000500100000
50000500020967
50000500020289
...

result:

ok 200000 lines

Test #43:

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

input:

200000
1 5000
0 1000000000
1 15000
0 1000000000
1 25000
0 1000000000
1 35000
0 1000000000
1 45000
0 1000000000
1 55000
0 1000000000
1 65000
0 1000000000
1 75000
0 1000000000
1 85000
0 1000000000
1 95000
0 1000000000
1 105000
0 1000000000
1 115000
0 1000000000
1 125000
0 1000000000
1 135000
0 1000000...

output:

103863342595000
150000000000000
134279654080000
150000000000000
121357390155000
150000000000000
150000000000000
112763275980000
150000000000000
150000000000000
122131661755000
150000000000000
149001998080000
148939595155000
150000000000000
150000000000000
132204615180000
150000000000000
143683831180...

result:

ok 200000 lines

Test #44:

score: 0
Accepted
time: 71ms
memory: 63068kb

input:

200000
0 1000000000
1 999995000
0 1000000000
1 999985000
0 1000000000
1 999975000
0 1000000000
1 999965000
0 1000000000
1 999955000
0 1000000000
1 999945000
0 1000000000
1 999935000
0 1000000000
1 999925000
0 1000000000
1 999915000
0 1000000000
1 999905000
0 1000000000
1 999895000
0 1000000000
1 999...

output:

118112700600000
150000000000000
150000000000000
135591214385000
150000000000000
150000000000000
115501859525000
150000000000000
124144759505000
141447992760000
147658552005000
104573347560000
149922500160000
149955776625000
150000000000000
147220389585000
140618187560000
150000000000000
148242937425...

result:

ok 200000 lines

Test #45:

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

input:

200000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 10000...

output:

161305000000000
102562000000000
200000000000000
200000000000000
200000000000000
200000000000000
103555000000000
158860000000000
158843000000000
196947000000000
200000000000000
200000000000000
174724000000000
185346000000000
191974000000000
163013000000000
200000000000000
200000000000000
109371000000...

result:

ok 200000 lines

Test #46:

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

input:

200000
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 1000000000
1 1
0 10...

output:

100000000100000
100000000051876
100000000100000
100000000049634
100000000059609
100000000034190
100000000090439
100000000100000
100000000021315
100000000024747
100000000035889
100000000030191
100000000100000
100000000030040
100000000100000
100000000100000
100000000003272
100000000100000
100000000100...

result:

ok 200000 lines

Test #47:

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

input:

200000
1 5000
0 1
1 15000
0 1
1 25000
0 1
1 35000
0 1
1 45000
0 1
1 55000
0 1
1 65000
0 1
1 75000
0 1
1 85000
0 1
1 95000
0 1
1 105000
0 1
1 115000
0 1
1 125000
0 1
1 135000
0 1
1 145000
0 1
1 155000
0 1
1 165000
0 1
1 175000
0 1
1 185000
0 1
1 195000
0 1
1 205000
0 1
1 215000
0 1
1 225000
0 1
1 235...

output:

50000000015319
50000000100000
50000000100000
50000000100000
50000000032151
50000000100000
50000000100000
50000000100000
50000000100000
50000000028304
50000000100000
50000000100000
50000000100000
50000000086398
50000000055189
50000000100000
50000000100000
50000000100000
50000000036484
50000000100000
...

result:

ok 200000 lines

Test #48:

score: 0
Accepted
time: 69ms
memory: 62928kb

input:

200000
1 1000000000
0 1
1 999990000
0 1
1 999980000
0 1
1 999970000
0 1
1 999960000
0 1
1 999950000
0 1
1 999940000
0 1
1 999930000
0 1
1 999920000
0 1
1 999910000
0 1
1 999900000
0 1
1 999890000
0 1
1 999880000
0 1
1 999870000
0 1
1 999860000
0 1
1 999850000
0 1
1 999840000
0 1
1 999830000
0 1
1 99...

output:

50000500033454
50000500045071
50000500053488
50000500091528
50000500022134
50000500041899
50000500100000
50000500100000
50000500100000
50000500057178
50000500100000
50000500067582
50000500100000
50000500015520
50000500100000
50000500100000
50000500100000
50000500100000
50000500100000
50000500100000
...

result:

ok 200000 lines

Test #49:

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

input:

200000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
1 1000000000
0 1
...

output:

100000000005785
100000000100000
100000000100000
100000000067455
100000000100000
100000000090780
100000000100000
100000000100000
100000000092608
100000000100000
100000000063454
100000000019564
100000000068264
100000000100000
100000000039599
100000000090953
100000000100000
100000000070996
100000000100...

result:

ok 200000 lines

Test #50:

score: 0
Accepted
time: 70ms
memory: 63112kb

input:

200000
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1...

output:

200000
144812
200000
109732
137090
200000
200000
122109
200000
176804
200000
200000
200000
174057
200000
108491
173632
200000
171865
200000
200000
127014
200000
200000
142473
191162
197331
200000
200000
200000
200000
200000
200000
200000
170156
199505
173222
200000
148260
200000
200000
200000
200000...

result:

ok 200000 lines

Extra Test:

score: 0
Extra Test Passed