QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672832#2386. FishermenYarema#AC ✓162ms18976kbC++141.5kb2024-10-24 19:24:142024-10-24 19:24:14

Judging History

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

  • [2024-10-24 19:24:14]
  • 评测
  • 测评结果:AC
  • 用时:162ms
  • 内存:18976kb
  • [2024-10-24 19:24:14]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;


struct fish
{
	LL x, y, i;
	
	bool operator<(const fish& f) const
	{
		return MP(x - y, i) < MP(f.x - f.y, f.i);
	}
};

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	
	int n, m, l;
	cin >> n >> m >> l;
	vector<PLL> f(n);
	FOR (i, 0, n)
		cin >> f[i].F >> f[i].S;
	sort(ALL(f), [](PLL a, PLL b)
	{
		return a.F + a.S < b.F + b.S;
	});
	set<fish> s;
	VL a(m);
	FOR (i, 0, m)
		cin >> a[i];
	VI idx(m);
	iota(ALL(idx), 0);
	sort(ALL(idx), [&a](int i, int j)
	{
		return a[i] < a[j];
	});
	VI ans(m);
	int j = 0;
	for (auto i : idx)
	{
		//cerr << i << ' ' << j << ' ' << f[j].F + f[j].S << ' ' << a[i] + l << '\n';
		while (j < n && f[j].F + f[j].S <= a[i] + l)
		{
			s.insert({f[j].F, f[j].S, j});
			j++;
		}
		//cerr << i << ' ' << SZ(s) << ' ';
		while (!s.empty())
		{
			fish p = *s.begin();
			//cerr << p.x << ' ' << p.y << ' ';
			if (p.x - p.y < a[i] - l)
				s.erase(s.begin());
			else
				break;
		}
		//cerr << SZ(s) << '\n';
		ans[i] = SZ(s);
	}
	FOR (i, 0, m)
	{
		cout << ans[i] << '\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2
2
3
2

result:

ok 4 lines

Test #2:

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

input:

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

output:

0
0
0
1
0
0
0
0
0

result:

ok 9 lines

Test #3:

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

input:

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

output:

3
5
5
4
5
5

result:

ok 6 lines

Test #4:

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

input:

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

output:

3
2
3
3
3
2
3
1
1

result:

ok 9 lines

Test #5:

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

input:

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

output:

3
1
0
3
1
1
0
4
4
4

result:

ok 10 lines

Test #6:

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

input:

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

output:

0
0
0
0
0
0
0
0
0

result:

ok 9 lines

Test #7:

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

input:

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

output:

1
1
1
1
1
1
1
1

result:

ok 8 lines

Test #8:

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

input:

2 10 7
7 6
5 7
10 4 2 10 7 3 4 10 6 9

output:

0
0
0
0
1
0
0
0
1
0

result:

ok 10 lines

Test #9:

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

input:

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

output:

2
3
3

result:

ok 3 lines

Test #10:

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

input:

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

output:

2
2
1
2
2
1

result:

ok 6 lines

Test #11:

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

input:

116 277 544035774
457555043 489407546
574193139 705098333
707698741 315720349
208325530 877497926
981245591 607323878
453761960 471636971
389550999 552349834
597663229 472586209
866184713 724626271
889644416 170170211
341359620 765577251
812521624 873855183
966390626 206729461
468280755 867064358
50...

output:

23
24
28
30
16
27
25
16
23
19
27
29
24
24
29
22
19
30
30
27
19
28
22
20
28
19
20
24
29
21
20
19
27
21
28
24
28
24
16
19
29
19
30
16
23
16
19
27
22
28
17
23
20
27
27
29
30
28
28
28
24
19
30
24
27
28
23
23
30
23
30
22
24
28
28
23
16
17
16
25
28
28
23
16
23
20
28
17
28
21
30
15
18
19
19
27
16
20
19
19
...

result:

ok 277 lines

Test #12:

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

input:

463 762 903869845
786821718 729012161
490386352 340752985
10435105 542536209
957723224 307861623
522793739 803954007
549649654 838603872
542850851 630740231
437060460 665817770
237583678 927714553
637913247 437467793
768979313 919594473
142107895 293238897
160231832 725480952
736448227 384006221
305...

output:

295
292
287
244
264
287
273
301
211
235
259
281
234
284
261
278
247
279
225
245
292
281
239
244
279
292
227
299
240
303
242
281
302
228
294
304
205
244
256
305
281
303
285
247
282
226
262
210
287
251
302
299
305
234
279
280
277
291
276
263
274
285
259
220
281
304
262
276
293
286
255
274
301
274
282
...

result:

ok 762 lines

Test #13:

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

input:

217 370 159194330
878544629 60322460
47450932 213955523
92454166 46547520
77179804 401805498
430009815 215843798
315613647 906176951
426307495 17690056
694540542 761726136
495150231 215776966
97389115 241550398
584368349 41844290
222568191 862210509
379439957 268265717
53094311 557214319
306412027 4...

output:

6
7
4
7
6
6
5
4
7
9
8
3
9
9
7
6
7
7
6
6
6
4
7
8
5
1
7
4
10
5
5
7
5
6
7
3
8
8
7
4
7
6
5
5
1
4
10
6
6
6
7
7
7
1
9
9
7
6
4
9
7
9
9
4
7
8
6
7
7
10
6
8
4
5
6
7
6
10
7
9
7
7
6
8
10
4
7
8
10
7
7
6
4
6
9
6
7
9
6
7
5
4
5
7
5
7
9
7
6
5
9
4
7
8
6
8
5
5
7
7
4
4
10
5
5
7
6
7
4
7
3
8
8
4
9
7
7
8
6
6
9
3
7
6
5
3
6...

result:

ok 370 lines

Test #14:

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

input:

951 179 239627598
469183479 291485925
836549649 192282063
642506257 847706963
499079460 542817908
518578176 137484185
250344740 334645873
758096228 876049936
39409828 628124509
719072995 938354096
917157755 253434807
538451622 704114329
944286020 624361308
143849690 598148235
922744285 22821906
5349...

output:

49
56
68
47
57
68
54
49
33
37
49
74
31
49
47
48
63
47
64
50
34
38
50
52
31
55
50
45
51
50
28
34
63
60
69
58
57
53
69
35
61
47
64
57
52
47
50
65
52
74
52
66
34
66
52
47
50
61
36
61
61
71
58
31
38
53
53
56
55
27
56
58
51
66
54
19
48
58
46
48
60
47
62
62
73
49
73
52
57
53
56
48
22
32
64
59
52
32
66
36
...

result:

ok 179 lines

Test #15:

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

input:

216 859 359463669
576258563 504958975
505295621 26909647
717867473 831046416
250209996 178391539
679125741 982160978
331803773 487071256
784160285 738868703
512434701 632186842
850057642 725541108
282335032 355374137
204670945 847966325
760330238 789337626
570919828 60114278
398979360 306301125
4493...

output:

28
20
17
19
29
20
17
29
32
24
27
17
26
18
28
27
24
23
26
29
28
28
30
30
26
24
29
29
28
27
26
17
28
32
17
17
29
26
29
25
31
28
28
20
30
24
30
17
19
22
29
25
29
29
29
23
29
28
17
30
27
24
20
32
20
24
30
28
28
28
26
29
26
17
30
17
29
28
31
29
30
31
20
28
24
23
29
29
26
19
16
24
24
30
31
28
26
27
17
22
...

result:

ok 859 lines

Test #16:

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

input:

1000 1000 328631903
817220293 325483346
561588637 776646900
268173178 996107582
193864575 470586288
706297084 337047649
171614359 308490327
678832840 864859416
776879498 467058560
759839566 218818005
164554547 798864664
309476468 874423709
383077154 716524253
957262866 706754187
456035864 630576356
...

output:

70
104
84
107
95
91
60
103
96
107
93
95
109
101
87
110
89
78
94
101
106
73
106
78
84
99
105
92
104
64
94
104
109
80
77
94
109
91
108
101
104
88
103
93
78
93
94
98
58
104
114
103
115
114
56
67
78
98
96
95
70
108
61
103
102
110
106
107
106
114
109
105
116
110
105
109
66
106
89
114
89
94
105
108
99
77
...

result:

ok 1000 lines

Test #17:

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

input:

1000 1000 964416952
795743240 359768401
570126497 290254180
134186918 285206875
978091536 786750965
918766626 657422206
233747133 872199489
547973617 144789051
529999063 372223248
316396701 900773186
986698465 607082400
956797251 686172668
171968565 234093088
262642964 971419137
482467196 392790837
...

output:

660
700
588
564
714
663
690
697
696
493
624
674
647
718
717
699
696
711
641
611
491
720
704
707
658
714
514
720
651
603
563
574
710
545
627
719
569
493
525
528
648
575
518
704
698
677
514
639
706
714
681
536
475
674
640
594
661
575
710
593
716
599
712
702
702
696
605
487
538
696
684
523
587
698
582
...

result:

ok 1000 lines

Test #18:

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

input:

1000 1000 501857095
248598021 510454741
162989742 494122790
416978345 110370030
733254249 825757914
709665308 376933094
893325344 630411503
673637301 179652999
271796978 583036936
586155773 151717867
720878454 458072410
549502259 297929474
82774578 904440622
369033419 255901201
367499813 376765794
7...

output:

250
269
133
160
269
204
219
175
248
255
145
253
275
158
191
131
269
135
264
204
157
271
267
182
233
265
220
138
169
269
268
183
269
269
181
226
200
183
209
269
270
268
229
271
143
263
263
269
266
220
204
262
136
246
269
187
130
263
204
259
178
211
246
254
268
189
172
248
191
152
252
266
170
205
144
...

result:

ok 1000 lines

Test #19:

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

input:

1000 1000 365895966
994571819 348480492
629380617 746010415
685345347 362966604
525184818 897318548
452703022 92260535
878991645 238586746
829348428 305783719
381745537 530517829
941153104 480922121
310604717 66130700
736268994 655716797
779283203 188918296
353132670 41080343
932061559 559733865
120...

output:

79
125
137
128
124
127
150
129
129
145
125
142
129
131
118
131
136
125
129
118
125
130
67
77
130
126
133
135
138
69
125
137
123
117
129
133
66
128
141
130
96
117
138
139
109
146
69
121
133
147
68
131
133
107
124
130
81
147
133
65
150
151
123
130
109
74
139
113
104
68
117
92
131
136
104
121
128
132
1...

result:

ok 1000 lines

Test #20:

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

input:

1000 1000 810971773
945150705 85113305
778870766 738079051
629138639 542825751
559501383 178015023
771696026 967250117
627147854 209687841
361775394 990969779
39929407 823136107
617700525 385301320
67326728 824646191
731336562 722637309
186864331 119098335
544613151 488658912
204979040 515074499
966...

output:

554
518
387
497
406
361
416
387
426
323
544
399
343
544
555
353
522
364
403
362
353
558
358
339
546
387
546
557
531
555
385
389
387
550
523
369
357
558
438
395
547
422
469
426
362
493
461
559
329
465
553
500
446
453
329
393
519
388
508
400
459
565
359
325
396
525
522
547
438
441
533
441
555
387
547
...

result:

ok 1000 lines

Test #21:

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

input:

198438 124963 409044218
41642069 61679249
940638404 276434118
907367379 127640656
31389798 168663706
687907985 118788498
93288337 219654337
236083455 520259483
533057346 701700887
877994309 133838978
783607145 970933648
607321533 788903860
295925100 473672369
660343670 5318255
841902243 399460882
24...

output:

33230
32435
29493
31820
29656
27710
21635
17058
32535
26179
22638
32001
20350
33259
32885
17929
29404
33101
31456
33082
21997
30431
32178
33076
27767
33157
25068
33001
29302
25072
24011
23773
33207
21669
28247
33092
33137
31900
28399
32359
31851
23030
23635
33040
32504
33259
33252
33056
31731
26910
...

result:

ok 124963 lines

Test #22:

score: 0
Accepted
time: 45ms
memory: 7292kb

input:

29729 192895 638473312
965836015 845422896
247217043 186275680
186358097 907957647
321831271 6475841
274208406 819636981
887004765 797478518
710489962 897466993
354800461 696907847
764116846 424144676
971099457 969365328
905819063 497120453
459544055 917560064
255312717 804341787
53480546 208986907
...

output:

10065
8455
10805
10778
11008
10370
7000
8609
6501
7894
9619
9051
10548
11609
7526
9172
6801
11526
8758
8087
7361
6674
10589
11209
11380
11619
10227
10840
9207
9661
9229
9577
10088
11234
7936
11208
8986
11623
11222
6536
10429
9516
11396
9143
9650
9258
10662
9269
11619
9993
8736
7758
11010
7786
10281
...

result:

ok 192895 lines

Test #23:

score: 0
Accepted
time: 52ms
memory: 8748kb

input:

67579 159187 702650386
490113701 264868293
815808167 94777458
314232565 732484462
983797923 215443164
490105721 638028098
77795231 669774936
288810132 351892771
754573668 397652291
66316314 786925960
708322418 376692170
189281235 652519417
787904635 453619826
469437947 835262868
873360614 601079955
...

output:

22698
17928
25637
30666
23700
30645
20809
29446
30230
30608
24438
22027
27418
28056
20042
19829
24267
26977
23520
21403
28075
25332
28088
30554
25674
29051
26691
25476
24976
23671
29616
29841
28109
24507
17928
29069
28114
29999
25516
24903
29760
27295
18713
20730
20467
24540
25290
30329
29773
24193
...

result:

ok 159187 lines

Test #24:

score: 0
Accepted
time: 22ms
memory: 4872kb

input:

38308 65791 268203630
250880255 910909505
523361707 640762518
710644454 693838231
405899653 692364786
597006214 727551983
584799041 180096964
225072093 242023207
542148356 575802405
900804570 780540722
692916522 872268416
978596066 540734099
884969153 528673813
857554510 211756262
650355211 74297202...

output:

2742
2747
2826
2793
2780
2786
2285
2766
2719
2492
2807
2750
2766
2142
2760
2071
2799
2604
2801
2799
2749
2819
2051
2403
2406
1908
2736
2750
2625
2657
2809
2811
2776
1832
2768
2771
2779
2710
2605
2778
2389
2782
2751
2151
2753
2738
2801
2781
2605
2570
2767
2271
2783
2778
1776
2775
2766
2771
2796
2722
...

result:

ok 65791 lines

Test #25:

score: 0
Accepted
time: 38ms
memory: 6720kb

input:

25089 139292 1000000000
805449929 84110876
933551081 871535236
136368135 265796367
588137308 328408384
4384315 194400613
243264949 501608124
470248019 918686306
55229924 684678720
876628298 468784001
823661731 138769303
135782718 278568461
233393194 916013929
974282848 513367968
638533605 423905063
...

output:

17751
17360
14498
17566
17114
14084
18769
18860
14825
15729
18538
16878
18728
15334
18746
18224
16759
18847
18593
18545
12450
14775
18333
18785
17246
14181
18071
18134
14368
16826
13395
16484
18836
12865
15592
18788
15762
18676
18837
18822
12950
14530
18599
17926
16234
13534
18124
18779
18807
18540
...

result:

ok 139292 lines

Test #26:

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

input:

119576 200000 536763005
44201949 300604676
182056841 390397575
956488791 65026532
131345670 802493334
651755284 207880980
85255884 64270459
772565891 105439850
770829341 689243692
550070230 637826588
255354175 47925317
287820677 446038856
101473785 471841154
893659595 91841645
127213081 441991239
38...

output:

20876
33190
32626
23903
24646
20645
31725
33591
32579
26594
24959
33407
32643
18863
34050
31431
30267
28896
33130
32907
23976
31613
33563
32925
31729
27456
27700
17570
23136
27906
21701
31267
32728
30713
18649
30747
33407
31062
21064
17290
33134
28660
31574
28250
31951
30006
29255
30281
26742
31445
...

result:

ok 200000 lines

Test #27:

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

input:

109537 200000 563366503
970144769 61863158
848547816 699222294
735836272 620402640
159181144 323527177
167684872 532733996
676647634 511987205
478531962 924004592
141497335 615967282
948862075 933814694
229989297 726906011
543857733 931408636
854369448 113270450
840786196 807164741
163167694 7114997...

output:

23299
19703
24464
20038
17983
29500
34223
18054
27978
32319
33610
34003
32582
34282
24870
34318
24177
31949
33598
30559
19276
18593
34016
33135
24925
23417
26313
31470
24817
27446
22812
20739
32734
27288
34364
32916
27089
26584
29679
31419
34016
18154
28358
27316
27753
31357
28205
33126
34020
34340
...

result:

ok 200000 lines

Test #28:

score: 0
Accepted
time: 43ms
memory: 6472kb

input:

21116 200000 93829414
985765582 226648274
991566201 552312968
993143687 780346193
434383336 157293468
730816770 206058337
234587499 98232967
804759797 53635466
54314986 471733848
730426520 431661948
843996431 244968318
395593512 373429384
811819722 554009676
121260648 847271461
861906893 238936956
9...

output:

170
171
198
187
199
177
160
154
206
191
197
165
152
188
158
176
190
160
194
210
190
186
183
196
161
122
157
160
201
180
181
210
197
129
193
192
206
200
189
120
195
189
200
197
98
206
170
190
128
175
195
184
185
150
141
180
189
197
198
163
209
189
180
189
200
190
195
180
177
190
186
185
211
190
191
2...

result:

ok 200000 lines

Test #29:

score: 0
Accepted
time: 57ms
memory: 7960kb

input:

59920 200000 367202823
364303483 619412351
194573334 120277729
212413635 946715299
114371523 801993270
576577406 35742054
744958339 484511750
848292044 29005259
875455047 314525816
339109777 869482043
146900484 536639575
551707635 207601154
727076915 474798479
118981598 683488720
776308307 747060149...

output:

7814
8138
8062
8151
8164
8146
7926
6708
8181
8154
8075
8163
7459
8184
7264
5198
7764
8105
5974
7452
8175
7968
8092
5191
7253
8175
7797
7081
8178
8116
8181
7966
5406
8167
5123
5507
8128
6083
8186
8022
8179
7658
4390
8076
6011
7672
6373
8138
4389
7967
7141
7330
6811
8159
4216
6105
8154
7255
8175
8139
...

result:

ok 200000 lines

Test #30:

score: 0
Accepted
time: 45ms
memory: 8644kb

input:

39036 200000 1000000000
799283568 434254671
127053923 640765163
839049155 635163621
254674072 502753659
798376597 425416960
740857091 931103072
676491252 768980508
223197293 817482174
406015094 627191750
837665643 650191149
986969080 303909066
212126697 15137912
974253883 134125876
749897629 9405307...

output:

27383
29141
27248
29193
23883
28942
28541
23733
20443
23853
26740
26299
24407
22571
28906
26480
29229
28169
23066
28167
29078
27269
28299
25741
28565
25669
28875
26249
25161
28335
26581
24073
28864
25180
20632
27840
22538
22963
20943
29113
22328
29201
24171
20113
23087
29235
25987
25782
26604
28401
...

result:

ok 200000 lines

Test #31:

score: 0
Accepted
time: 52ms
memory: 6816kb

input:

200000 17474 102440111
639519695 580146359
985701958 187696276
4193538 565099514
998903530 691772672
33941422 388766722
276993615 615384519
776880101 544569829
937277596 846336355
398696191 439016864
136989560 450241396
56062487 597042324
10216594 520007483
958158988 85934597
758610970 950875677
709...

output:

2128
2018
2182
2057
2163
2098
1994
2159
2165
2113
2087
2138
2170
2017
2136
2184
2179
2099
2092
2121
2134
2146
2179
2097
2008
2136
2123
1998
2155
2134
2009
2104
2086
2144
2167
2135
2133
2173
1710
2009
1995
2017
2144
2079
2178
1525
1956
2027
1723
1493
2079
2163
2013
2188
2015
2133
2157
2008
2160
2117
...

result:

ok 17474 lines

Test #32:

score: 0
Accepted
time: 90ms
memory: 9668kb

input:

200000 181513 230399451
629817752 304285596
29324187 98950627
206272412 451289060
132476724 943363261
394769810 9051613
121670267 336666531
805646737 793484357
317428695 525760243
254279540 496031035
183308214 435178159
961611610 86832836
541099785 247662332
940352550 54742855
51839942 391412390
518...

output:

10029
10617
10621
10633
10602
10037
8059
10639
6470
10543
7596
10637
10638
10439
9140
10536
10600
10089
7477
10693
10542
9968
10502
10326
10529
10619
10619
8691
8363
10656
10522
9733
10529
10488
10502
10267
10564
6031
8176
5998
10530
10684
10438
10603
9796
10682
10719
9821
10032
10599
8596
10448
106...

result:

ok 181513 lines

Test #33:

score: 0
Accepted
time: 162ms
memory: 17556kb

input:

200000 135435 989439053
865436263 506548523
476275871 867462481
355112530 298087764
57730814 827782132
675560741 559674460
714491436 248329383
427409541 671909542
511817744 765239008
587687614 898072025
636422007 615016855
315888445 905401697
786096273 936724425
77672213 408850157
630645106 98409548...

output:

139103
132153
129889
122863
133581
136856
139175
147622
138834
135739
113800
132940
146795
129815
147864
145770
134254
142999
106750
147516
135387
142540
145685
140736
145010
128135
111245
143011
143143
142201
126660
137798
143841
100336
119171
101909
112039
147968
147849
99136
125409
131744
132406
...

result:

ok 135435 lines

Test #34:

score: 0
Accepted
time: 84ms
memory: 10148kb

input:

200000 93295 447054364
680283102 878507185
883125078 86755215
847973006 738531088
739730040 423861412
309762127 554849853
581873554 226163694
550133327 195716046
37046180 346654242
474212482 557897146
424413364 489805979
208122399 57473758
50006603 669441495
686595105 123580280
527929334 909536247
4...

output:

28919
35103
39717
39432
39384
39707
26264
31825
37460
35553
39643
39712
27598
39404
28342
38499
39720
24124
32554
26307
29982
39178
39765
32688
35149
39027
21953
21928
26725
35899
22828
38381
21216
39399
32465
21802
37325
33545
36723
36904
28780
35599
39258
38433
28909
39637
38657
39535
39134
23183
...

result:

ok 93295 lines

Test #35:

score: 0
Accepted
time: 128ms
memory: 17020kb

input:

200000 85341 1000000000
641624739 654095466
201209661 382351657
742935497 999646092
542986296 994031388
970832223 465819068
658050104 424789754
7417723 428187792
268968574 208396418
507971668 156459731
428292029 399129667
779468461 382780897
775480487 651087064
523943951 332282428
869060855 63419968...

output:

118313
119075
108592
133429
133211
118678
115723
147588
149367
149865
136835
126263
112392
119880
104312
109672
144371
147665
108923
145914
149139
146451
148685
149818
148245
137729
138059
119550
100935
118828
144900
101520
149852
121434
132101
137393
109010
118592
140329
118406
129313
128748
131646...

result:

ok 85341 lines

Test #36:

score: 0
Accepted
time: 135ms
memory: 16812kb

input:

200000 200000 836371316
10278152 274677426
839108967 251303741
932422743 684248212
427791371 707641247
462876208 222065704
468548229 388685194
586366641 329791655
708893520 747655967
442714190 247065533
198849144 963537461
864302672 518173708
25694240 472529623
695923537 378146215
77241084 880505795...

output:

109078
117017
116250
89257
73893
117249
76639
77924
114108
78076
116119
115148
113960
116995
103051
102679
104110
103242
75030
115159
110812
117190
81459
116465
110057
116970
88082
117217
86693
100828
85047
85438
112402
117198
117150
107370
117156
108580
113544
102886
89558
79275
101422
107698
11697...

result:

ok 200000 lines

Test #37:

score: 0
Accepted
time: 83ms
memory: 9540kb

input:

200000 200000 75295633
393293591 170276501
206434686 908083180
689147918 919257185
120768520 210267063
569487116 668574025
852891599 270756817
368132619 97939079
855705527 895872365
973921144 922734313
848206934 332487827
77538482 876370256
320828535 863223455
671953552 650159922
572838297 442243264...

output:

1073
1097
1160
1117
1185
1111
1193
1125
1171
1105
1126
1114
1011
1179
1130
1126
1130
1140
1111
1135
1195
1170
1132
1126
611
1132
1122
1173
1159
1124
1141
1170
1192
1159
584
1128
1105
1146
1193
1090
1132
1122
1159
1119
1141
1115
1113
1199
1112
895
1137
1112
1182
1146
1095
1179
1118
1132
1129
1128
112...

result:

ok 200000 lines

Test #38:

score: 0
Accepted
time: 112ms
memory: 12720kb

input:

200000 200000 496747978
930452312 910804444
140625767 51634292
366622699 231375149
602795204 529623933
302445281 777161585
654916631 816787868
414506547 65527884
217672530 514856959
908999535 378292501
12921148 115807430
256907830 978294101
274068467 174233477
203515070 396808012
348959589 304505286...

output:

48914
42852
44116
42510
49036
48484
45559
48883
47887
41280
41756
49167
48453
46692
48539
36575
47751
48966
32055
48877
28543
44823
48858
31790
34399
46602
46541
24723
27911
27523
45432
48086
48955
45494
43180
46587
49165
45455
45271
49072
49047
48498
41475
29434
48822
46816
47103
36060
30637
38398
...

result:

ok 200000 lines

Test #39:

score: 0
Accepted
time: 159ms
memory: 17752kb

input:

200000 200000 926535600
102013527 261040838
872385480 482721451
492904207 645591382
345092987 572697935
896628848 556920193
894721370 254330452
737447647 775001595
171596115 80994313
407537265 970976842
68525638 870979792
548546928 743439691
657802376 988467102
379976412 827296174
782796897 12282380...

output:

134422
130433
103034
89297
135331
135529
116713
118214
109713
126506
121203
86079
134731
107559
97210
114291
88525
125446
110600
119541
87216
102306
133113
88350
116132
134351
128432
135384
133865
118127
110242
132339
108593
129346
132912
122998
118591
123762
135585
120423
95100
133184
105367
120294...

result:

ok 200000 lines

Test #40:

score: 0
Accepted
time: 152ms
memory: 18976kb

input:

200000 200000 1000000000
233321736 643398603
356529135 949185418
384533030 341853196
203474285 236896709
245084227 735767727
476786295 573102801
481224095 518737340
726920280 573479563
602052448 892871554
612055892 428577450
152030157 291231749
550907245 298973305
727799074 877151198
787092749 10559...

output:

125170
146940
123296
137548
143150
149693
126202
107674
109877
143783
133811
149355
127019
143495
149503
143506
144758
102467
105718
117324
112664
149693
146473
140349
147268
149675
144137
128351
147759
143681
145172
106331
149487
144934
101439
130838
135909
143887
143552
119932
141507
118215
102601...

result:

ok 200000 lines

Test #41:

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

input:

1 2 4
3 3
2 5

output:

1
0

result:

ok 2 lines

Test #42:

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

input:

2 1 4
3 3
4 4
4

output:

2

result:

ok single line: '2'

Test #43:

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

input:

2 2 1000000000
1000000000 1000000000
55 55
1000000000 999999999

output:

2
1

result:

ok 2 lines