QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313155#5264. Wyprzedzanietuxuanming202465 217ms21740kbC++142.8kb2024-01-24 16:20:552024-01-24 16:20:56

Judging History

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

  • [2024-01-24 16:20:56]
  • 评测
  • 测评结果:65
  • 用时:217ms
  • 内存:21740kb
  • [2024-01-24 16:20:55]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include "txm/debug.h"
#endif
using namespace std;
typedef long long ll;
const int N=100005;
struct frac
{
	__int128 a,b;
	frac operator + (const frac &x)const
	{
		__int128 aa=b*x.a+a*x.b,bb=b*x.b,g=__gcd(aa,bb);
		return (frac){aa/g,bb/g};
	}
	frac operator - (const frac &x)const
	{
		__int128 aa=a*x.b-b*x.a,bb=b*x.b,g=__gcd(aa,bb);
		return (frac){aa/g,bb/g};
	}
	frac operator * (const frac &x)const 
	{
//		cerr<<"! "<<(int)a<<" "<<(int)b<<'\n';
		__int128 aa=a*x.a,bb=b*x.b,g=__gcd(aa,bb);
		return (frac){aa/g,bb/g};
	}
	frac operator / (const frac &x)const 
	{
//		cerr<<"! "<<(int)x.a<<" "<<(int)x.b<<'\n';
		return (frac){a,b}*(frac){x.b,x.a};
	}
	bool operator > (const frac &x)const
	{
		return a*x.b>b*x.a;
	}
	bool operator < (const frac &x)const
	{
		return a*x.b<b*x.a;
	}
	bool operator == (const frac &x)const
	{
		return a*x.b==b*x.a;
	}
	void Debug() {cerr<<"Debug "<<(int)a<<" "<<(int)b<<'\n';}
};
typedef frac ld;
int n,D,d[N],x[N],nxt[N],p[N][17],ans;
ld V,v[N],t[N],pos[N];
ll s[N];
bool iseq(ld x,ld y) {return x==y;}
ld ask(int a,ld tt)
{
	if(tt<t[a]) return (frac){x[a],1}+v[a]*tt;
	int y=a;
	for(int i=16;i>=0;i--)
		if(p[y][i]&&(tt>t[p[y][i]]||iseq(t[p[y][i]],tt))) y=p[y][i];
	tt=tt-t[y];
	return pos[y]+v[p[y][0]]*tt-(frac){s[y]-s[a],1};
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.ans","w",stdout);
	int w,m;
	scanf("%d %d %d %d",&n,&D,&w,&m),V=(frac){w,m};
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d %d %d",x+i,d+i,&w,&m);
		v[i]=(frac){w,m},s[i]=s[i-1]+d[i];
	}
	nxt[n]=n+1,t[n]=(frac){(__int128)1e19,1},pos[n]=(frac){x[n],1};
	for(int i=n-1;i>=1;i--)
	{
		nxt[i]=i+1;
		while(nxt[i]<=n&&(v[i]<v[nxt[i]]||iseq(v[i],v[nxt[i]]))) nxt[i]=nxt[nxt[i]];
		if(nxt[i]>n) {t[i]=(frac){(__int128)1e19,1},pos[i]=(frac){x[i],1}; continue;}
		int to=nxt[i];
		ld tt=(frac){x[to]-x[i]-(s[to]-s[i]),1}/(v[i]-v[to]);
		if(tt>t[to]||iseq(tt,t[to]))
		{
			for(int j=16;j>=0;j--)
			{
				int k=p[nxt[i]][j];
				if(!k) continue;
				tt=(frac){x[k]-x[i]-(s[k]-s[i]),1}/(v[i]-v[k]);
				if(tt>t[k]||iseq(tt,t[k])) to=k;
			}
			to=p[to][0];
		}
		p[i][0]=to;
		t[i]=(frac){x[to]-x[i]-(s[to]-s[i]),1}/(v[i]-v[to]);
		pos[i]=(frac){x[i],1}+v[i]*t[i];
		for(int j=1;1<<j<=n;j++) p[i][j]=p[p[i][j-1]][j-1];
	}
	for(int i=1;i<=n;i++)
	{
		ld tt;
		int j=i;
		if(V*t[i]>(frac){x[i]-d[i],1}) tt=(frac){x[i]-d[i],1}/(V-v[i]);
		else
		{
			for(int k=16;k>=0;k--)
			{
				int fa=p[j][k];
				if(!fa||t[fa]==(frac){(__int128)1e19,1}) continue;
				if(V*t[fa]<pos[fa]-(frac){s[fa]-s[i],1}) j=fa;
			}
			j=p[j][0];
			tt=(frac){x[j]-(s[j]-s[i-1]),1}/(V-v[j]);
		}
		ld L=ask(i,tt)-(frac){d[i],1}-ask(i-1,tt);
		if(i==1||L>(frac){D,1}||iseq((frac){D,1},L)) ans++;
	}
	printf("%d",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 77ms
memory: 17708kb

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: 57ms
memory: 17632kb

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: 74ms
memory: 16968kb

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: 57ms
memory: 17712kb

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: 64ms
memory: 17648kb

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: 65ms
memory: 16876kb

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: 1ms
memory: 9876kb

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: 77ms
memory: 17176kb

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: 83ms
memory: 17652kb

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: 87ms
memory: 17924kb

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: 82ms
memory: 17864kb

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: 85ms
memory: 17640kb

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: 77ms
memory: 17892kb

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: 0ms
memory: 12036kb

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: 12024kb

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: 4ms
memory: 12244kb

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: 4ms
memory: 14016kb

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: 10236kb

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: 2ms
memory: 10236kb

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: 3ms
memory: 13980kb

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: 3ms
memory: 13980kb

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: 1ms
memory: 11960kb

input:

1 1000000000 520 597
1000000000 1 780 953

output:

1

result:

ok single line: '1'

Test #23:

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

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: 2ms
memory: 10204kb

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: 10260kb

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: 2ms
memory: 12000kb

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: 2ms
memory: 12248kb

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: 9972kb

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: 2ms
memory: 12048kb

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: 0ms
memory: 9964kb

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: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #31:

score: 35
Accepted
time: 217ms
memory: 21728kb

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: -35
Wrong Answer
time: 216ms
memory: 21740kb

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:

15544

result:

wrong answer 1st lines differ - expected: '15536', found: '15544'