QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790229#7078. Tower of the SorcererlarryyuWA 53ms45512kbC++202.1kb2024-11-28 08:50:522024-11-28 08:50:52

Judging History

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

  • [2024-11-28 08:50:52]
  • 评测
  • 测评结果:WA
  • 用时:53ms
  • 内存:45512kb
  • [2024-11-28 08:50:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define Maxh 200000
#define int long long
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define pii pair<int,int> 
int n,a0;
struct node{
	int a,h;
	friend bool operator<(node x,node y){
		return x.a<y.a;
	}
}b[200020];
double slope(pii x,pii y){
	return 1.0*(x.se-y.se)/(x.fi-y.fi);
}
int calc(pii x,int y){
	return x.se-y*x.fi;
}
struct tree{
	int hd;
	vector<pii>v;
}tr[800080];
void upd(int x,pii k){
	while(tr[x].v.size()-tr[x].hd>1){
		pii v1=tr[x].v[tr[x].v.size()-1];
		pii v2=tr[x].v[tr[x].v.size()-2];
		if(k.fi==v1.fi){
			if(k.se>=v1.se) return ;
			else tr[x].v.pop_back();
		}else{
			if(slope(k,v1)<slope(k,v2)) break;
			tr[x].v.pop_back();
		}
	}
	tr[x].v.push_back(k);
}
int qry(int x,int k){
	if(tr[x].v.size()-tr[x].hd<=0) return 1e18;
	while(tr[x].v.size()-tr[x].hd>1){
		pii v1=tr[x].v[tr[x].hd],v2=tr[x].v[tr[x].hd+1];
		if(slope(v1,v2)<=k) break;
		tr[x].hd++;
	}
	return calc(tr[x].v[tr[x].hd],k);
}
void update(int x,int l,int r,int L,int R,pii v){
	if(l>=L&&r<=R) return upd(x,v),void();
	int mid=l+r>>1;
	if(L<=mid) update(ls,l,mid,L,R,v);
	if(R>=mid+1) update(rs,mid+1,r,L,R,v);
}
int query(int x,int l,int r,int k,int v){
	int tmp=qry(x,v);
	if(l==r) return tmp;
	int mid=l+r>>1;
	if(k<=mid) tmp=min(tmp,query(ls,l,mid,k,v));
	else tmp=min(tmp,query(rs,mid+1,r,k,v));
	return tmp;
}
void alter(int x,int y){
	for(int i=1;i<=Maxh;i+=x){
		update(1,1,Maxh,i,min((int)Maxh,i+x-1),{(i-1)/x,y});
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>n>>a0;
	for(int i=1;i<=n;i++){
		cin>>b[i].a>>b[i].h;
	}
	sort(b+1,b+1+n);
	int st=upper_bound(b+1,b+1+n,node{a0,0})-b;
	alter(a0,0);
	int minn=1e18;
	for(int i=st;i<=n;i++){
		int x=query(1,1,Maxh,b[i].h,-b[i].a);
		x-=(b[i].h-1)/b[n].a*b[i].a;
		minn=min(minn,x);
		if(b[i+1].a!=b[i].a){
			alter(b[i].a,minn);
			if(i!=n) minn=1e18;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans+=(b[i].h-1)/max(b[n].a,a0)*b[i].a;
	if(a0<=b[n].a) ans+=minn;
	cout<<ans;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 42ms
memory: 43660kb

input:

4 1
3 2
4 4
5 6
1 6

output:

9

result:

ok single line: '9'

Test #2:

score: 0
Accepted
time: 32ms
memory: 36204kb

input:

5000 679
84191 46042
81916 66659
74636 72443
10252 57443
21838 54620
84896 58466
20832 29643
45949 20576
50399 51434
56472 90759
68909 94348
39459 1731
81207 17614
26465 11775
93861 24936
25017 64663
21042 37570
32903 68583
68840 58347
93849 10841
10190 77131
10595 1959
57163 59047
16066 89850
73741...

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 36ms
memory: 36108kb

input:

5000 685
67283 21828
19841 367
69908 57925
63894 10753
20139 20595
672 47788
81010 57483
53755 96758
85049 78636
94198 12795
97299 86489
57399 56590
30519 63514
92072 5714
60572 8651
25620 13514
27482 51652
88352 27272
4391 23458
43759 57471
95084 88191
53782 96875
52546 33731
95458 5643
75049 42685...

output:

60515

result:

ok single line: '60515'

Test #4:

score: 0
Accepted
time: 28ms
memory: 36640kb

input:

5000 883
57988 4889
27548 3497
47774 97848
73725 83535
43075 12741
86312 87522
98386 29435
88105 19813
50656 83340
32721 37465
84421 14671
92169 37187
33163 53370
95155 35577
63396 86337
20931 57282
80964 12797
84905 95122
7530 7623
1393 58436
9609 91063
92309 31959
37789 98189
74209 33091
64400 530...

output:

142420

result:

ok single line: '142420'

Test #5:

score: 0
Accepted
time: 44ms
memory: 37240kb

input:

5000 110
81857 71124
57698 64343
80952 96284
15190 95432
51153 64223
39943 25603
77013 72711
94708 24951
64786 9225
54307 29867
2166 9420
38155 28813
96118 90751
85381 30858
17457 43971
38450 20480
36831 31955
86436 3116
71718 45322
2141 92627
36585 66945
8885 99790
49929 5604
25126 14766
78673 4804...

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 30ms
memory: 35612kb

input:

5000 852
68512 97389
60972 88659
73325 90709
87906 83485
39089 40758
25295 95321
61154 18959
19137 97232
40721 17563
3359 33010
484 29851
3964 60841
88065 81476
1622 35273
28703 97697
72577 9099
16043 92977
37261 95232
41086 16776
38139 94039
79650 24363
30987 95332
81397 67793
52508 71034
22631 725...

output:

0

result:

ok single line: '0'

Test #7:

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

input:

5000 23
49957 100000
97978 100000
66997 100000
70406 100000
62250 100000
71093 100000
14758 100000
59859 100000
81605 100000
50139 100000
97303 100000
23626 100000
38523 100000
5028 100000
59461 100000
99559 100000
5150 100000
21343 100000
5738 100000
81487 100000
87427 100000
67101 100000
8692 1000...

output:

251733189

result:

ok single line: '251733189'

Test #8:

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

input:

5000 10
100000 64460
100000 96604
100000 64490
100000 95985
100000 52966
100000 9407
100000 2618
100000 50047
100000 37993
100000 94354
100000 47586
100000 91096
100000 18738
100000 88600
100000 37646
100000 88124
100000 43502
100000 56950
100000 81193
100000 14352
100000 54736
100000 14837
100000 1...

output:

0

result:

ok single line: '0'

Test #9:

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

input:

5000 51
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 10000...

output:

196000000

result:

ok single line: '196000000'

Test #10:

score: 0
Accepted
time: 18ms
memory: 36184kb

input:

5000 2
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 2400
50 24...

output:

11807600

result:

ok single line: '11807600'

Test #11:

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

input:

5000 11
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 10...

output:

45450000

result:

ok single line: '45450000'

Test #12:

score: 0
Accepted
time: 18ms
memory: 35868kb

input:

2 1
1 100000
100000 1

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 27ms
memory: 37888kb

input:

2 1
1 3
3 100

output:

297

result:

ok single line: '297'

Test #14:

score: 0
Accepted
time: 16ms
memory: 32324kb

input:

100 178
157 16066
189 16201
134 18255
190 12359
142 15665
192 17956
120 14861
194 18445
169 13814
190 10523
198 11396
188 13529
164 16559
138 13158
154 13246
123 12920
190 19092
181 19819
147 18071
188 11408
134 17172
148 14664
192 17871
143 18116
109 19693
179 12343
180 17090
150 12711
200 19798
17...

output:

1168450

result:

ok single line: '1168450'

Test #15:

score: 0
Accepted
time: 5ms
memory: 30464kb

input:

100 9236
7864 75108
8699 16535
376 50738
5639 97958
1784 75293
9729 88266
8655 81610
9938 74490
8566 17220
9666 21635
8362 43274
1995 15239
3613 63840
8632 64439
2242 12081
3354 13214
2507 81554
7578 31837
9960 13140
1185 18627
8361 27567
3592 45065
5251 40472
9311 31355
5034 65035
5613 74538
6905 2...

output:

2511795

result:

ok single line: '2511795'

Test #16:

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

input:

100 4368
5639 95168
7156 47518
8137 57053
1704 48642
3005 91592
7450 64182
3425 38836
5516 77818
7703 67882
8744 42240
1318 42471
6684 39471
5381 43548
1742 67073
1030 70989
2157 15781
3176 51219
6351 36894
4604 5818
9460 39265
5931 90339
7116 37275
8648 16323
9825 10441
8072 42787
9503 68159
7434 9...

output:

2538739

result:

ok single line: '2538739'

Test #17:

score: 0
Accepted
time: 13ms
memory: 33128kb

input:

100 259
80 62302
302 57717
193 13269
771 58062
219 26436
554 22639
108 77948
970 89532
447 19679
760 97544
48 44667
211 94414
610 96029
527 37537
17 61669
995 86153
168 57342
987 11576
693 20776
174 55470
168 71708
681 10275
432 22361
106 80512
853 31365
845 57897
207 37804
107 15058
662 26829
30 57...

output:

2565739

result:

ok single line: '2565739'

Test #18:

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

input:

100 94765
44791 9234
39635 44708
39512 84352
32154 66011
95490 38673
69605 76862
27992 84300
90563 32269
13845 16554
22423 62907
50980 71481
21655 7696
96806 72538
12431 84328
93712 11554
44475 91283
7050 94813
29168 64499
24721 33319
80563 34144
28949 60657
3264 38471
86940 51106
26629 76327
87933 ...

output:

0

result:

ok single line: '0'

Test #19:

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

input:

1000 195
187 11608
136 14918
135 15113
159 11782
159 13355
151 14945
103 14301
153 11918
187 15797
159 15577
175 16979
178 15105
132 17688
160 11025
145 13008
176 14603
166 15739
116 18242
194 19461
117 18584
104 19047
142 12937
128 14092
158 15208
146 12487
197 17821
138 19564
150 11753
142 18718
1...

output:

11220118

result:

ok single line: '11220118'

Test #20:

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

input:

1000 3689
2418 25992
2569 90297
1939 65017
2894 50479
3342 93448
601 95293
126 34177
2683 14222
3692 55360
4435 70569
2233 15930
2285 94214
1696 48218
2605 18093
264 70767
2177 87976
3069 38238
3128 13627
2069 95572
664 31911
1153 38299
2847 18232
663 94897
526 61842
3458 36552
1804 43399
3010 18977...

output:

26297784

result:

ok single line: '26297784'

Test #21:

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

input:

1000 3308
1336 99208
2118 65085
1307 44413
602 84005
4354 55223
721 54826
3699 58727
1247 99323
4329 93508
2854 69922
3612 84741
4387 35136
3016 74005
807 37010
2316 82232
2184 97191
4810 33549
2994 67161
3423 89070
3359 21907
2994 90806
4974 84031
3994 66716
2170 62740
1393 77560
4841 54589
2048 49...

output:

27618897

result:

ok single line: '27618897'

Test #22:

score: 0
Accepted
time: 10ms
memory: 32696kb

input:

1000 5690
5272 18563
2208 13185
9929 714
6120 93411
4027 65417
3274 6417
1557 15728
6169 20252
7863 64435
9467 7163
6526 52042
8295 47015
2836 21585
2188 76447
7822 43273
4361 76646
3978 12213
8282 55488
1772 69598
1097 68665
4831 22992
2052 25566
6487 25818
5874 87873
6847 87090
6630 15385
3127 178...

output:

25274270

result:

ok single line: '25274270'

Test #23:

score: 0
Accepted
time: 33ms
memory: 37808kb

input:

1000 613
622 12278
294 36627
327 50583
79 54719
527 64809
242 20366
611 71052
924 86998
685 68548
586 42802
289 60911
299 23970
761 69745
362 21439
354 57080
205 25072
197 73906
601 17218
511 26906
699 69989
777 51114
128 20489
848 21377
486 17410
582 61455
649 53973
423 62451
55 44187
854 75577
444...

output:

26928349

result:

ok single line: '26928349'

Test #24:

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

input:

1000 9061
4223 28214
1308 25048
2247 9513
5616 51812
1155 29478
6145 51360
1187 96078
6523 91752
9627 68567
2715 5130
9317 88298
9572 94956
2317 16166
4076 28740
7715 1500
2191 62367
9053 31921
4699 12987
3378 52095
6867 7340
8256 79347
4317 96091
1446 22865
1124 34274
5819 7116
3126 49745
2837 9431...

output:

22397306

result:

ok single line: '22397306'

Test #25:

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

input:

1000 93761
13042 45072
30325 40700
72475 32486
18918 54911
83363 66278
43430 12654
35635 60291
67455 81519
88983 64792
18976 18541
26303 98722
20826 7192
4350 6177
47363 92867
3086 45596
49463 11493
59403 42842
47058 13305
43315 63433
68535 28670
1452 50266
60108 4919
75230 80419
11932 85707
73877 1...

output:

0

result:

ok single line: '0'

Test #26:

score: -100
Wrong Answer
time: 29ms
memory: 37816kb

input:

100000 1
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 100000
1 1...

output:

1000000009999900000

result:

wrong answer 1st lines differ - expected: '9999900000', found: '1000000009999900000'