QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#313449#5264. Wyprzedzaniedyj133446100 ✓134ms15032kbC++141.3kb2024-01-24 19:24:202024-01-24 19:24:21

Judging History

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

  • [2024-01-24 19:24:21]
  • 评测
  • 测评结果:100
  • 用时:134ms
  • 内存:15032kb
  • [2024-01-24 19:24:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,D,x[N],dd[N],ans=1;
long long sum[N];
__float128 V,v[N],k[N],b[N],d[N],T1[N],T2[N];
int zhan[N],top;
__float128 readV()
{
	int x,y;
	cin>>x>>y;
	return (__float128)x/y;
}
__float128 calc(__float128 k1,__float128 b1,__float128 k2,__float128 b2)
{
	return (b2-b1)/(k1-k2);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>D,V=readV();
	for(int i=1;i<=n;i++)cin>>x[i]>>dd[i],v[i]=readV(),sum[i]=sum[i-1]+dd[i];
	for(int i=1;i<=n;i++)k[i]=v[i],b[i]=x[i]-sum[i];
	d[1]=1e18;
	for(int i=n;i;i--)
	{
		while(top&&(k[zhan[top]]>=k[i]||calc(k[zhan[top]],b[zhan[top]],k[i],b[i])>=d[top]))top--;
		zhan[++top]=i;
		if(top!=1)d[top]=calc(k[zhan[top]],b[zhan[top]],k[zhan[top-1]],b[zhan[top-1]]);
		__float128 K=V,B=b[i]-(x[i]+D);
		int l=1,r=top;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(K*d[mid]+B>=k[zhan[mid]]*d[mid]+b[zhan[mid]])l=mid+1;
			else r=mid-1;
		}
		T1[i]=calc(K,B,k[zhan[r]],b[zhan[r]]);
		B=b[i]-(x[i]-dd[i]);
		l=1,r=top;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(K*d[mid]+B>=k[zhan[mid]]*d[mid]+b[zhan[mid]])l=mid+1;
			else r=mid-1;
		}
		T2[i]=calc(K,B,k[zhan[r]],b[zhan[r]]);
	}
	for(int i=1;i<n;i++)if(T1[i]<=T2[i+1])ans++;
	cout<<ans;
	return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 52ms
memory: 14556kb

input:

100000 9 445 874
1653 9 34 792
2736 336 34 792
21599 862 34 792
23975 188 34 792
41891 401 34 792
62576 193 34 792
74285 567 34 792
78959 2850 34 792
85316 452 34 792
92188 217 34 792
97244 3526 34 792
106804 599 34 792
112500 1352 34 792
120610 581 34 792
123644 213 34 792
123754 16 34 792
125589 4...

output:

99905

result:

ok single line: '99905'

Test #2:

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

input:

100000 42 423 459
37434 62 373 551
55489 515 373 551
58121 1271 373 551
62626 1237 373 551
85240 1500 373 551
100367 2450 373 551
103859 766 373 551
105195 647 373 551
113654 79 373 551
116413 2078 373 551
123362 157 373 551
128320 670 373 551
130075 1030 373 551
146426 397 373 551
155828 1195 373 5...

output:

99539

result:

ok single line: '99539'

Test #3:

score: 0
Accepted
time: 53ms
memory: 14580kb

input:

100000 514 651 267
5878 637 349 559
8958 1820 349 559
19500 1747 349 559
26299 1243 349 559
27584 995 349 559
30038 128 349 559
41755 367 349 559
46773 28 349 559
57112 3790 349 559
77098 1945 349 559
79912 346 349 559
81176 1071 349 559
96565 1741 349 559
99869 1267 349 559
105062 1131 349 559
1225...

output:

94212

result:

ok single line: '94212'

Test #4:

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

input:

100000 6903 385 122
27659 90 660 238
29771 3 660 238
33082 45 660 238
36254 55 660 238
37436 36 660 238
49934 126 660 238
56662 21 660 238
64037 20 660 238
70132 223 660 238
73123 37 660 238
74391 106 660 238
87544 26 660 238
90127 179 660 238
95773 66 660 238
108314 4 660 238
111360 113 660 238
115...

output:

49159

result:

ok single line: '49159'

Test #5:

score: 0
Accepted
time: 59ms
memory: 14556kb

input:

100000 47429 212 203
11292 49 249 293
19281 41 249 293
38517 20 249 293
65772 24 249 293
73342 63 249 293
86818 112 249 293
95250 201 249 293
98973 183 249 293
132629 18 249 293
138479 87 249 293
139269 40 249 293
140399 74 249 293
141852 100 249 293
157957 20 249 293
160317 24 249 293
160534 53 249...

output:

970

result:

ok single line: '970'

Test #6:

score: 0
Accepted
time: 55ms
memory: 14704kb

input:

100000 891884 617 488
5243 119 597 691
6747 15 597 691
14373 119 597 691
17883 52 597 691
20388 113 597 691
50660 73 597 691
58923 161 597 691
63414 61 597 691
76445 157 597 691
84324 38 597 691
88647 197 597 691
97447 498 597 691
106705 34 597 691
119011 122 597 691
150042 63 597 691
164835 102 597...

output:

2

result:

ok single line: '2'

Test #7:

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

input:

1 1000000000 761 455
1000000000 1 737 595

output:

1

result:

ok single line: '1'

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #8:

score: 20
Accepted
time: 51ms
memory: 14564kb

input:

100000 9 984 1
13277 1519 1 998
50255 1248 1 991
76049 794 1 979
78294 128 1 978
84461 2332 1 969
117959 2101 1 943
138836 3303 1 932
139565 418 1 932
143805 216 1 928
150460 1323 1 928
153651 105 1 924
159235 175 1 898
165846 1922 1 891
174840 2016 1 886
184405 800 1 880
200807 711 1 878
210013 174...

output:

99963

result:

ok single line: '99963'

Test #9:

score: 0
Accepted
time: 53ms
memory: 14724kb

input:

100000 31 997 1
1041 5 1 998
14054 1061 1 982
20888 3270 1 970
40091 1054 1 940
44674 353 1 937
45648 271 1 931
48417 659 1 926
57508 1070 1 904
63225 55 1 900
66451 1733 1 898
68665 579 1 895
70696 1548 1 894
100516 530 1 883
103117 68 1 868
108640 723 1 862
113044 310 1 857
116930 421 1 857
120527...

output:

99800

result:

ok single line: '99800'

Test #10:

score: 0
Accepted
time: 48ms
memory: 14524kb

input:

100000 822 1000 1
2968 768 1 1000
21579 31 1 999
25773 1431 1 996
27447 1036 1 982
34954 255 1 982
50345 3194 1 967
59666 469 1 960
95568 2012 1 942
116776 4462 1 938
130891 1467 1 929
135657 148 1 893
137747 2 1 880
141581 2150 1 879
160529 225 1 872
170809 1500 1 872
171997 727 1 861
182071 189 1 ...

output:

91841

result:

ok single line: '91841'

Test #11:

score: 0
Accepted
time: 55ms
memory: 14704kb

input:

100000 5379 992 1
16416 11 1 997
20030 59 1 997
31208 298 1 994
35979 19 1 986
37550 80 1 981
54939 36 1 913
58490 123 1 913
62154 34 1 909
62613 20 1 862
68902 63 1 861
74561 18 1 846
82073 36 1 842
101997 112 1 842
109319 10 1 819
127017 44 1 810
132013 108 1 809
148866 11 1 804
183313 20 1 802
19...

output:

59408

result:

ok single line: '59408'

Test #12:

score: 0
Accepted
time: 55ms
memory: 14620kb

input:

100000 38590 1000 1
9503 122 1 994
9862 113 1 984
12816 72 1 951
18952 35 1 937
46312 281 1 931
59176 99 1 930
60739 30 1 928
66948 152 1 910
69161 62 1 894
74109 22 1 886
85758 114 1 881
106054 21 1 880
120363 81 1 877
134005 21 1 865
136631 39 1 864
147254 102 1 851
154084 73 1 850
158311 3 1 816
...

output:

3428

result:

ok single line: '3428'

Test #13:

score: 0
Accepted
time: 56ms
memory: 14568kb

input:

100000 990557 987 1
11760 171 1 995
13375 117 1 988
16115 232 1 983
48046 63 1 970
58961 121 1 940
62062 40 1 933
64806 3 1 909
92075 144 1 905
107413 27 1 902
109695 80 1 899
120050 37 1 895
140820 4 1 875
146407 7 1 874
155458 143 1 861
162536 104 1 857
171054 174 1 856
175081 69 1 841
176075 37 1...

output:

199

result:

ok single line: '199'

Test #14:

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

input:

1 1000000000 859 157
1000000000 1 583 629

output:

1

result:

ok single line: '1'

Subtask #3:

score: 35
Accepted

Test #15:

score: 35
Accepted
time: 3ms
memory: 13888kb

input:

1000 5 716 3
632 108 255 785
1891 115 699 140
2143 130 778 315
3409 155 450 486
7330 57 351 675
10955 24 959 657
13151 127 37 429
13903 115 749 82
15213 37 267 276
15906 168 971 23
17068 74 751 600
18435 207 306 662
18493 4 463 490
18882 60 381 293
22184 64 888 663
27168 89 962 190
28751 121 122 898...

output:

527

result:

ok single line: '527'

Test #16:

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

input:

1000 20 917 8
1820 78 441 641
3590 90 486 512
6487 194 536 942
7056 123 266 270
8508 87 130 622
8990 30 654 463
10808 23 741 79
10932 27 228 776
11215 111 458 864
11778 38 751 153
12021 15 321 435
12053 9 162 741
12341 120 496 802
14246 23 431 808
16027 7 508 119
18356 168 362 909
20542 68 465 53
21...

output:

416

result:

ok single line: '416'

Test #17:

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

input:

1000 941 795 2
2446 276 652 673
3067 23 907 79
4023 57 20 189
4076 10 22 364
4263 46 101 752
4508 23 680 464
4777 178 638 58
5426 15 674 162
5537 43 75 564
5882 163 753 662
8162 125 142 638
9026 35 862 797
9117 57 689 398
11859 83 584 712
13277 17 897 881
13389 36 638 525
13790 20 763 810
16538 117 ...

output:

373

result:

ok single line: '373'

Test #18:

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

input:

1000 2625 10 1
477305 370 10 7
1151540 1000 7 10
1893809 12 9 1
3502666 718 4 6
3611320 296 6 6
5699350 260 3 8
8394591 596 3 10
8668961 750 2 4
11183997 981 8 7
13008836 37 10 8
14044159 2729 2 3
14287006 121 1 3
15373289 938 8 1
15724757 1165 1 4
16641191 1541 9 6
16980331 1060 7 3
17356572 4031 8...

output:

176

result:

ok single line: '176'

Test #19:

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

input:

1000 95619 10 1
26818 358 5 2
1122928 1616 6 3
1716816 175 7 10
3119287 836 9 3
3421179 3539 5 8
3570557 357 8 3
3790272 927 3 3
4240818 1211 1 9
5172443 1049 4 9
6239353 52 9 3
6675674 1504 5 3
8167258 66 9 1
9517371 2632 4 9
10547195 527 4 5
11014094 143 3 7
11841288 402 7 4
11968651 1527 5 1
1257...

output:

178

result:

ok single line: '178'

Test #20:

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

input:

1000 688304 10 1
620285 151 4 6
1034959 76 5 6
1225719 208 3 4
1713426 1012 6 7
3854628 1429 1 7
3927030 761 9 7
4437632 651 6 7
6426941 275 4 6
7028698 581 2 8
10549176 267 8 5
11653349 431 1 1
12080963 1598 6 4
13450599 672 10 5
15247541 747 7 7
15264944 2386 8 4
18172172 403 2 4
18625291 352 2 6
...

output:

161

result:

ok single line: '161'

Test #21:

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

input:

1000 1000000 10 1
2936901 3583 8 3
4644448 1954 4 3
5097512 417 10 9
5811378 323 2 6
6649104 220 8 7
7757879 327 4 5
8882610 1914 7 10
10770045 192 9 1
11903208 1663 1 4
12418289 272 9 4
12915573 195 2 5
14421535 356 3 5
14548681 2142 1 3
15042434 1059 4 5
15846240 2657 9 9
18290147 744 4 2
18982461...

output:

147

result:

ok single line: '147'

Test #22:

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

input:

1 1000000000 520 597
1000000000 1 780 953

output:

1

result:

ok single line: '1'

Test #23:

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

input:

1000 1 422 1
1095880 16014 3 841
1298884 76349 5 762
1702910 111571 5 568
1912705 25792 9 830
3745225 105212 9 728
3781023 30467 11 821
10618469 1096 13 907
11803677 82134 8 535
12637880 22279 6 391
13484141 76745 15 854
14951827 5716 10 543
15505787 232803 13 598
18572957 581420 10 457
20108441 712...

output:

933

result:

ok single line: '933'

Test #24:

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

input:

1000 27 605 2
1191466 54930 2 658
1613580 23200 3 715
1962744 24271 5 774
5027396 61091 3 416
5262460 76466 3 318
5462017 38352 5 514
5662349 13044 7 627
7902840 45266 10 879
8627486 150735 3 253
10770123 38265 14 949
12223404 97148 11 692
13090647 30038 13 712
14117271 100358 4 207
14322056 56073 2...

output:

949

result:

ok single line: '949'

Test #25:

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

input:

1000 489 576 2
438069 158776 2 680
896880 30966 4 777
2877163 246055 5 822
3774194 149311 4 629
4484416 71503 8 904
5441560 280164 5 514
5782141 63987 9 827
6312864 16095 11 889
6816587 23988 12 925
7516219 336352 2 111
7969756 288358 11 573
8515585 134018 13 588
8972225 46577 11 477
9799954 62797 1...

output:

951

result:

ok single line: '951'

Test #26:

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

input:

1000 4113 10 1
869434 77 1 10
1776850 445 1 10
2302328 2 1 10
3249965 216 7 6
3828364 595 1 10
8371011 754 1 9
8390016 62 1 9
10409005 668 1 9
10942850 179 1 9
11197527 3047 1 9
11265410 2071 1 9
11960682 152 1 8
12592083 3229 1 8
14640521 3919 1 8
17632213 194 1 8
18488270 837 1 8
19259259 147 1 8
...

output:

613

result:

ok single line: '613'

Test #27:

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

input:

1000 95698 10 1
1066719 292 1 10
3705384 1683 1 10
3801293 1773 1 10
6188356 1084 1 10
6309758 746 1 10
6877872 1506 1 10
7597138 1022 1 10
7851504 1409 1 10
9479948 689 1 10
10160908 671 1 10
11748366 930 1 10
12647207 1559 1 10
12896307 576 1 10
13777984 965 1 10
14977389 31 1 10
15072854 63 1 9
1...

output:

508

result:

ok single line: '508'

Test #28:

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

input:

1000 164349 10 1
1843692 789 1 10
2961691 1175 1 10
4644838 916 1 10
5743333 1840 1 10
5787040 225 1 10
7878423 3245 1 10
8542061 126 1 10
8920175 201 1 10
9122458 483 1 10
10402874 1156 1 10
11254248 456 1 10
12296407 554 1 10
13627737 1025 1 10
14062934 56 1 10
15916407 138 1 10
16521950 1065 1 10...

output:

502

result:

ok single line: '502'

Test #29:

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

input:

1000 999000 3 1
2160793 1003 1 2
3160863 1071 1 2
3865062 496 1 2
6138641 470 1 2
7137768 128 1 2
8138166 1400 1 2
8457449 505 1 2
9456512 65 1 2
10456359 847 1 2
11455513 156 1 2
12172673 417 1 2
13049976 5 1 2
14049235 261 1 2
15049075 841 1 2
15373229 1208 1 2
15487309 81 1 2
16486620 313 1 2
174...

output:

155

result:

ok single line: '155'

Test #30:

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

input:

1000 2 530 1
165209 2379 652 2
587177 150 642 4
1789008 110 941 10
2951053 2429 629 11
4852075 240 865 16
5588441 119 801 15
5637541 1231 895 17
7321840 2016 576 11
8149905 92 802 17
8896679 587 811 22
8987004 6409 995 29
9203597 1755 873 27
10082558 938 122 4
10670219 330 716 24
10845051 76 444 17
...

output:

997

result:

ok single line: '997'

Subtask #4:

score: 35
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #31:

score: 35
Accepted
time: 110ms
memory: 14484kb

input:

100000 3 1000 1
1972 308 514 200
9917 166 786 713
13938 121 485 320
35714 1953 416 655
41519 120 54 771
50457 2426 200 844
58336 2488 423 471
69551 947 571 260
81080 38 295 327
82694 1171 968 440
87921 105 16 332
98168 945 652 988
104997 372 996 111
106036 591 75 279
108266 1057 162 743
115958 831 4...

output:

15680

result:

ok single line: '15680'

Test #32:

score: 0
Accepted
time: 121ms
memory: 14732kb

input:

100000 16 992 1
12313 51 907 724
14435 194 863 289
31923 179 666 478
41253 1231 233 695
44236 2087 834 456
57558 500 385 769
67717 2565 754 550
101559 361 934 386
111778 45 493 575
138322 2701 120 964
141329 442 167 325
142331 872 123 442
171455 148 988 762
172565 48 999 778
179149 75 14 431
193615 ...

output:

15536

result:

ok single line: '15536'

Test #33:

score: 0
Accepted
time: 111ms
memory: 14532kb

input:

100000 345 982 1
5016 620 233 19
17934 1318 903 450
20679 1235 235 336
58905 1045 320 161
78329 603 54 453
84947 89 515 173
88488 837 455 690
94741 1567 79 484
96806 305 324 615
97776 157 2 476
101013 256 602 176
137199 690 681 218
141530 1479 608 961
161327 493 352 809
171595 174 110 240
180892 766...

output:

15295

result:

ok single line: '15295'

Test #34:

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

input:

100000 3741 991 1
128 62 128 578
5458 666 201 411
40863 41 458 115
46152 191 193 73
60573 176 415 235
60843 63 309 964
61767 10 782 148
65048 41 136 708
81793 31 279 142
83727 168 462 212
91094 63 1 203
112286 138 472 470
115868 81 102 124
118474 10 585 272
123383 37 444 134
132631 76 568 220
134014...

output:

15254

result:

ok single line: '15254'

Test #35:

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

input:

100000 93558 986 1
613 3 877 672
3474 44 289 797
4363 50 435 680
34651 407 524 445
55007 235 73 847
58000 52 533 188
59176 344 373 632
61509 193 405 598
62951 115 613 957
63008 40 482 610
67505 376 808 634
78185 24 868 797
91217 104 652 990
98242 18 526 436
117733 65 466 900
126105 150 517 978
12969...

output:

3563

result:

ok single line: '3563'

Test #36:

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

input:

100000 248182 990 1
6977 818 172 389
8680 88 36 898
20135 249 453 752
24783 110 359 338
30831 10 65 857
34976 119 198 927
38778 141 747 731
49485 8 440 535
57422 172 208 935
58260 60 310 742
75296 129 218 910
77760 189 453 912
81155 208 346 210
81327 7 886 26
81648 35 814 686
116143 42 547 514
11946...

output:

241

result:

ok single line: '241'

Test #37:

score: 0
Accepted
time: 2ms
memory: 11840kb

input:

1 1000000000 124 408
1000000000 1 10 142

output:

1

result:

ok single line: '1'

Test #38:

score: 0
Accepted
time: 89ms
memory: 14584kb

input:

100000 9 944 1
29863 270 1 1000
32720 4 1 998
36762 25 1 978
43009 1249 1 976
45171 266 1 966
88348 852 1 966
97078 290 1 961
106486 1032 1 953
111574 37 1 952
115830 180 1 942
126974 784 1 911
131587 1361 1 907
136185 202 1 899
138912 302 1 896
145920 2214 1 858
157636 296 1 857
165145 1706 1 855
1...

output:

61119

result:

ok single line: '61119'

Test #39:

score: 0
Accepted
time: 93ms
memory: 14832kb

input:

100000 53 978 1
2887 105 1 995
6365 453 1 988
20158 418 1 980
46449 1936 1 964
87970 1254 1 905
110888 391 1 901
111210 148 390 334
113474 94 1 886
129550 934 1 882
136345 957 1 882
141966 25 1 872
149505 895 1 854
156175 641 1 840
165651 1436 1 838
190082 1246 1 819
194476 409 1 810
198342 250 1 80...

output:

61157

result:

ok single line: '61157'

Test #40:

score: 0
Accepted
time: 98ms
memory: 14704kb

input:

100000 794 994 1
613 181 1 1000
15490 158 1 995
18992 458 1 991
36516 610 1 965
42219 1808 1 960
45432 1934 1 953
49788 1640 1 950
56477 1747 1 939
61878 593 1 936
86022 28 1 929
89371 514 1 928
95096 161 1 913
109274 410 1 913
125917 3384 1 909
147950 949 1 905
153797 1243 1 887
163642 1121 1 871
1...

output:

55601

result:

ok single line: '55601'

Test #41:

score: 0
Accepted
time: 93ms
memory: 14576kb

input:

100000 8387 1000 1
18001 45 1 959
22726 26 1 922
23901 213 1 919
26170 32 1 915
26548 49 1 883
27789 67 1 881
53342 49 1 854
53738 14 1 848
54942 37 1 846
57476 92 1 844
60225 21 1 842
67170 112 1 841
68854 63 1 836
71832 111 1 807
73909 23 1 800
104312 46 1 794
121555 48 1 784
122145 240 1 783
1241...

output:

27208

result:

ok single line: '27208'

Test #42:

score: 0
Accepted
time: 94ms
memory: 14692kb

input:

100000 29732 998 1
8054 49 1 997
13469 82 1 983
28109 49 1 981
31795 12 1 973
63618 73 1 961
93928 168 1 944
100713 19 1 943
102463 112 1 937
106794 89 1 918
112478 46 1 915
157902 163 627 70
161011 399 1 913
206079 216 1 910
215780 42 1 900
217675 22 1 881
241874 147 1 835
243226 74 1 829
251305 41...

output:

4042

result:

ok single line: '4042'

Test #43:

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

input:

100000 659392 999 1
10668 45 1 998
12468 161 1 976
13823 35 1 974
20032 13 1 972
38202 99 1 961
38534 50 1 947
69236 128 1 924
70438 91 1 917
89608 151 1 912
111318 240 1 891
112035 12 1 891
112567 93 1 886
112634 36 1 861
134910 103 1 860
137829 29 1 827
167062 43 1 823
169237 139 1 797
172899 61 1...

output:

233

result:

ok single line: '233'

Test #44:

score: 0
Accepted
time: 126ms
memory: 14572kb

input:

100000 4 986 1
15881 280 966 1
20223 1080 964 1
31551 1643 944 1
42161 1737 921 1
43787 230 918 1
59093 1984 917 1
60428 889 916 1
93020 598 916 1
108702 1905 893 1
110893 198 888 1
119688 182 885 1
142970 1158 882 1
147068 1283 864 1
157857 1072 855 1
159135 374 853 1
177536 637 845 1
182900 340 84...

output:

99450

result:

ok single line: '99450'

Test #45:

score: 0
Accepted
time: 94ms
memory: 14572kb

input:

100000 1 3 1
3 1 989 352
6 1 697 294
9 1 851 317
12 1 907 431
15 1 505 221
18 1 535 263
21 1 691 257
24 1 951 422
27 1 449 157
30 1 176 85
33 1 962 465
36 1 195 77
39 1 295 139
42 1 696 275
45 1 860 361
48 1 805 269
51 1 733 268
54 1 842 297
57 1 863 350
60 1 533 228
63 1 985 368
66 1 772 371
69 1 9...

output:

402

result:

ok single line: '402'

Test #46:

score: 0
Accepted
time: 91ms
memory: 14528kb

input:

100000 1 3 1
3 1 669 257
6 1 947 465
9 1 517 197
12 1 865 429
15 1 859 326
18 1 658 249
21 1 407 139
24 1 290 131
27 1 771 266
30 1 872 291
33 1 809 364
36 1 233 106
39 1 418 175
42 1 879 413
45 1 579 239
48 1 509 183
51 1 722 289
54 1 943 439
57 1 655 281
60 1 739 282
63 1 989 357
66 1 411 166
69 1...

output:

170

result:

ok single line: '170'

Test #47:

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

input:

100000 1 3 1
3 1 737 261
6 1 599 261
9 1 937 438
12 1 863 399
15 1 621 289
18 1 434 159
21 1 757 284
24 1 676 337
27 1 666 301
30 1 591 283
33 1 854 325
36 1 652 233
39 1 661 301
42 1 521 185
45 1 688 239
48 1 394 165
51 1 489 220
54 1 547 265
57 1 443 184
60 1 992 381
63 1 524 197
66 1 443 210
69 1...

output:

101

result:

ok single line: '101'

Test #48:

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

input:

100000 1 987 1
27625 815 669 761
39037 642 118 858
56279 2756 536 179
57911 1072 996 156
60998 766 116 381
73632 342 176 454
73853 78 158 31
96877 2075 364 819
109738 18 280 508
124700 615 988 942
134622 1580 727 102
141885 1199 920 677
156201 3115 676 751
157073 826 322 112
182169 928 922 645
18575...

output:

15518

result:

ok single line: '15518'

Test #49:

score: 0
Accepted
time: 111ms
memory: 14568kb

input:

100000 46 999 1
5355 217 668 897
9172 579 330 767
12568 1419 50 902
20672 799 276 10
26094 751 860 436
35079 87 940 540
44677 154 807 245
47931 1415 814 956
51370 103 802 560
54575 212 306 733
58939 2478 406 614
69391 201 715 304
75332 143 868 903
76183 351 451 891
82915 1522 855 906
85318 359 111 9...

output:

15703

result:

ok single line: '15703'

Test #50:

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

input:

100000 240 983 1
3348 931 199 511
7633 140 253 969
11211 1578 431 150
15948 1557 387 691
27017 670 176 582
32139 1149 582 326
44230 1066 719 321
48081 83 651 437
53282 381 940 928
97719 1180 784 818
105937 476 354 523
113505 444 487 508
127271 148 558 249
131290 3873 593 997
163447 792 572 484
16848...

output:

15458

result:

ok single line: '15458'

Test #51:

score: 0
Accepted
time: 98ms
memory: 14524kb

input:

100000 3035 979 1
773 79 110 139
36665 31 737 567
56640 101 464 430
86279 40 911 149
96408 110 770 14
103766 212 293 129
107260 97 260 2
113980 51 128 982
119221 268 192 427
180913 22 676 708
182675 48 243 915
183209 74 601 937
189606 279 691 150
202184 178 757 421
212950 103 684 462
214500 135 455 ...

output:

15473

result:

ok single line: '15473'

Test #52:

score: 0
Accepted
time: 106ms
memory: 14520kb

input:

100000 79134 982 1
829 93 827 564
4513 98 843 589
5801 156 999 142
13488 71 229 47
35675 136 459 10
38409 40 345 230
72663 55 471 808
81336 150 27 579
101180 42 869 622
103452 113 351 109
108106 49 234 544
112184 69 675 267
119374 66 321 161
124751 136 748 494
133321 228 498 801
158346 241 263 557
1...

output:

4540

result:

ok single line: '4540'

Test #53:

score: 0
Accepted
time: 113ms
memory: 14552kb

input:

100000 276414 994 1
3036 14 332 988
4091 75 206 682
6342 140 486 198
19357 238 567 574
24108 116 722 189
28109 112 896 541
30129 384 821 342
30244 24 621 421
32572 47 44 584
42276 211 659 921
46513 44 518 866
54155 42 945 26
55051 57 500 814
60774 44 344 451
64458 10 674 229
75346 69 404 891
76573 2...

output:

132

result:

ok single line: '132'

Test #54:

score: 0
Accepted
time: 2ms
memory: 12000kb

input:

1 1000000000 215 173
1000000000 1 192 444

output:

1

result:

ok single line: '1'

Test #55:

score: 0
Accepted
time: 98ms
memory: 14556kb

input:

100000 1 1000 1
6432 330 1 999
14993 2787 1 988
16109 923 1 986
22109 1297 1 980
33420 207 1 959
37943 713 1 955
52203 402 1 946
62822 36 1 941
80745 159 1 930
85621 859 1 871
86969 496 1 825
117193 1539 1 818
117543 183 1 800
130187 525 1 782
134944 555 1 774
140676 67 1 770
149967 1094 1 761
15891...

output:

60317

result:

ok single line: '60317'

Test #56:

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

input:

100000 14 996 1
6038 1004 1 994
12359 1834 1 988
14186 120 1 988
15578 66 1 978
31011 1020 562 968
33884 117 1 936
37712 13 1 921
46098 1095 1 914
58144 1885 1 905
65260 2646 1 882
67667 627 1 878
78139 2383 1 875
84934 56 1 861
97529 848 1 832
102628 3168 1 826
125047 527 1 819
126444 732 1 816
140...

output:

60109

result:

ok single line: '60109'

Test #57:

score: 0
Accepted
time: 97ms
memory: 14564kb

input:

100000 312 980 1
2353 1306 1 996
28685 1801 1 995
34791 1060 1 988
41552 1687 1 980
62443 478 1 979
68160 1762 1 977
91764 1341 293 659
97458 766 1 971
103906 1282 566 822
118709 2305 1 947
123289 464 1 935
124309 160 1 933
127010 985 1 930
146363 117 1 925
154440 20 1 906
156166 673 1 897
159720 19...

output:

58067

result:

ok single line: '58067'

Test #58:

score: 0
Accepted
time: 98ms
memory: 14700kb

input:

100000 3220 999 1
17026 403 1 997
20586 13 1 989
34251 102 1 987
41178 84 1 979
56273 9 1 978
65278 16 1 967
78029 194 1 964
88005 93 1 954
92525 38 1 950
118411 1 1 949
119283 11 1 937
123908 6 1 928
141440 50 1 922
147500 70 1 920
156116 13 1 907
159753 33 1 884
180208 115 1 881
182996 145 1 871
1...

output:

44439

result:

ok single line: '44439'

Test #59:

score: 0
Accepted
time: 95ms
memory: 14472kb

input:

100000 62022 998 1
17482 19 1 1000
36001 28 1 994
55419 5 1 991
63488 337 1 989
82275 162 1 974
105278 4 1 958
108957 75 1 935
114705 137 1 925
124468 40 1 906
157598 146 1 893
166838 17 1 891
225674 34 1 878
232669 4 1 868
250037 17 1 865
253193 50 1 864
283339 210 1 852
284337 12 1 839
289486 397 ...

output:

1089

result:

ok single line: '1089'

Test #60:

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

input:

100000 295455 998 1
24447 16 1 990
34069 170 1 989
34439 279 1 968
34794 62 1 966
41039 202 1 954
49679 24 1 944
50014 47 1 941
50098 29 1 927
51632 265 1 926
55431 90 1 912
83277 115 1 905
128556 181 1 894
140393 50 1 894
140727 20 1 876
141367 189 585 106
147642 62 1 859
162448 63 1 858
172168 347...

output:

444

result:

ok single line: '444'

Test #61:

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

input:

100000 4 998 1
16041 1367 997 1
18258 1209 983 1
32981 381 982 1
37521 891 969 1
40714 603 926 1
48181 159 924 1
49507 698 915 1
51085 373 913 1
70766 952 907 1
80458 453 907 1
82863 107 895 1
90067 899 891 1
106678 157 878 1
107699 874 862 1
109472 204 852 1
121945 3032 852 1
145848 1086 804 1
1595...

output:

99510

result:

ok single line: '99510'

Test #62:

score: 0
Accepted
time: 89ms
memory: 14676kb

input:

100000 1 3 1
3 1 820 299
6 1 616 223
9 1 929 323
12 1 993 371
15 1 746 275
18 1 443 195
21 1 841 350
24 1 732 251
27 1 833 396
30 1 623 221
33 1 608 233
36 1 664 275
39 1 260 121
42 1 651 319
45 1 931 319
48 1 669 257
51 1 123 49
54 1 985 348
57 1 713 308
60 1 822 317
63 1 782 385
66 1 714 347
69 1 ...

output:

398

result:

ok single line: '398'

Test #63:

score: 0
Accepted
time: 91ms
memory: 14588kb

input:

100000 1 3 1
3 1 373 180
6 1 949 411
9 1 547 256
12 1 878 375
15 1 695 282
18 1 416 187
21 1 963 382
24 1 977 434
27 1 505 236
30 1 637 228
33 1 854 291
36 1 664 301
39 1 752 291
42 1 928 329
45 1 949 349
48 1 614 207
51 1 707 344
54 1 752 355
57 1 993 362
60 1 857 320
63 1 292 137
66 1 781 316
69 1...

output:

184

result:

ok single line: '184'

Test #64:

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

input:

100000 1 3 1
3 1 891 311
6 1 476 181
9 1 726 355
12 1 788 335
15 1 941 350
18 1 927 463
21 1 307 113
24 1 670 251
27 1 661 327
30 1 910 439
33 1 402 161
36 1 602 251
39 1 628 309
42 1 978 343
45 1 698 291
48 1 795 298
51 1 968 453
54 1 642 239
57 1 727 334
60 1 479 231
63 1 983 475
66 1 998 389
69 1...

output:

101

result:

ok single line: '101'

Test #65:

score: 0
Accepted
time: 87ms
memory: 14484kb

input:

100000 1 1000 499
3 1 991 991
6 1 988 992
9 1 1000 1000
12 1 988 990
15 1 996 1000
18 1 993 1000
21 1 982 987
24 1 992 995
27 1 988 988
30 1 991 995
33 1 1000 1000
36 1 983 997
39 1 990 996
42 1 983 1000
45 1 992 1000
48 1 993 1000
51 1 998 999
54 1 986 994
57 1 989 990
60 1 994 999
63 1 993 998
66 ...

output:

855

result:

ok single line: '855'

Test #66:

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

input:

100000 1 1000 499
3 1 992 998
6 1 991 1000
9 1 986 992
12 1 988 997
15 1 992 999
18 1 986 994
21 1 999 1000
24 1 987 996
27 1 989 995
30 1 996 999
33 1 993 998
36 1 994 998
39 1 986 989
42 1 1000 1000
45 1 985 993
48 1 982 984
51 1 986 990
54 1 990 995
57 1 988 1000
60 1 997 998
63 1 980 982
66 1 99...

output:

661

result:

ok single line: '661'

Test #67:

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

input:

100000 1 1000 499
3 1 987 990
6 1 986 996
9 1 987 991
12 1 989 998
15 1 991 996
18 1 984 987
21 1 999 1000
24 1 981 990
27 1 997 998
30 1 982 992
33 1 998 999
36 1 1000 1000
39 1 991 995
42 1 992 996
45 1 986 991
48 1 995 995
51 1 984 989
54 1 996 997
57 1 990 991
60 1 993 995
63 1 981 985
66 1 988 ...

output:

362

result:

ok single line: '362'

Test #68:

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

input:

100000 1 1000 499
3 1 998 999
6 1 986 995
9 1 999 999
12 1 981 984
15 1 997 999
18 1 986 988
21 1 987 998
24 1 982 1000
27 1 986 988
30 1 990 990
33 1 980 990
36 1 997 998
39 1 984 993
42 1 984 992
45 1 995 999
48 1 1000 1000
51 1 995 997
54 1 980 999
57 1 997 999
60 1 980 1000
63 1 995 995
66 1 985...

output:

405

result:

ok single line: '405'

Test #69:

score: 0
Accepted
time: 86ms
memory: 14524kb

input:

100000 1 1000 499
3 1 989 990
6 1 985 989
9 1 990 994
12 1 985 999
15 1 997 1000
18 1 991 999
21 1 983 1000
24 1 994 995
27 1 997 997
30 1 980 992
33 1 985 999
36 1 981 983
39 1 993 993
42 1 993 997
45 1 1000 1000
48 1 990 990
51 1 1000 1000
54 1 984 994
57 1 992 994
60 1 981 988
63 1 985 991
66 1 9...

output:

638

result:

ok single line: '638'

Test #70:

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

input:

15 1 1000 499
3 1 990 992
6 1 1 1000
9 1 1 944
142857148 1 990 997
142857151 1 1 1000
285714290 1 988 991
285714293 1 1 1000
428571432 1 999 1000
428571435 1 1 1000
571428574 1 980 981
571428577 1 1 1000
714285716 1 988 998
714285719 1 1 1000
857142858 1 986 997
857142861 1 1 1000

output:

8

result:

ok single line: '8'

Extra Test:

score: 0
Extra Test Passed