QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#788765#7078. Tower of the SorcererzhichengWA 28ms27568kbC++142.0kb2024-11-27 18:13:482024-11-27 18:13:49

Judging History

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

  • [2024-11-27 18:13:49]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:27568kb
  • [2024-11-27 18:13:48]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
int now;
ll dp[N],d[N];
struct ss{
	int a,h;
	bool operator<(ss b){
		return a<b.a;
	}
}p[N];
struct qu{
	int now,las;
	vector<pair<ll,ll> >p;
	inline ll calc(int x,ll y){
		return p[x].first*y+p[x].second;
	}
	inline ll query(ll x){
		while(las+1<p.size()&&calc(las,x)>=calc(las+1,x)){
			las++;
		}
		return las<p.size()?calc(las,x):1e18;
	}
	inline bool pd(int now,ll x,ll y){
		if(p[now-1].first==x){
			if(y<=p[now-1].second){
				return 1;
			}
			return 0;
		}
		return now>=2&&calc(now-1,::now)>=x*::now+y;
	}
	inline void ins(ll x,ll y){
		while(now>=1&&pd(now,x,y)){
			now--;
			p.pop_back();
		}
		p.push_back({x,y});
		now++;
	}
}s[N<<2];
inline void update(int x,int y,pair<ll,ll>z,int l,int r,int rt){
	int mid=(l+r)>>1;
	if(x<=l&&y>=r){
		s[rt].ins(z.first,z.second);
		return;
	}
	if(x<=mid){
		update(x,y,z,l,mid,rt<<1);
	}
	if(y>=mid+1){
		update(x,y,z,mid+1,r,rt<<1|1);
	}
}
inline void upd(int x){
	for(int i=0,cnt=0;i<=1e5;i+=x,cnt++){
		if(max(i,1)>min((int)1e5,i+x-1)){
			continue;
		}
		update(max(i,1),min((int)1e5,i+x-1),{cnt,dp[x]},1,1e5,1);
	}
}
inline ll query(int x,int l,int r,int rt){
	int mid=(l+r)>>1;
	if(l==r){
		return s[rt].query(now);
	}
	return min(s[rt].query(now),x<=mid?query(x,l,mid,rt<<1):query(x,mid+1,r,rt<<1|1));
}
int main(){
	int n,a;
	scanf("%d%d",&n,&a);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&p[i].a,&p[i].h);
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		p[i].h--;
		d[i]=1ll*(p[i].h/max(a,p[n].a))*p[i].a;
	}
	if(a>=p[n].a){
		goto lass;
	}
	for(int i=1;i<=1e5;i++){
		dp[i]=1e18;
	}
	dp[a]=0;
	upd(a);
	for(int i=1;i<=n;i++){
		if(p[i].a<=a){
			continue;
		}
		now=p[i].a;
		dp[p[i].a]=min(dp[p[i].a],query(p[i].h,1,1e5,1)-d[i]);
		if(p[i].a!=p[i+1].a){
			upd(p[i].a);
		}
	}
	lass:;
	for(int i=1;i<=n;i++){
		dp[p[n].a]+=d[i];
	}
	printf("%lld",dp[p[n].a]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 23ms
memory: 25100kb

input:

4 1
3 2
4 4
5 6
1 6

output:

9

result:

ok single line: '9'

Test #2:

score: 0
Accepted
time: 19ms
memory: 21512kb

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: 26ms
memory: 21984kb

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: 19ms
memory: 21536kb

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: 27ms
memory: 22388kb

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: 14ms
memory: 21268kb

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: -100
Wrong Answer
time: 28ms
memory: 27568kb

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:

251743666

result:

wrong answer 1st lines differ - expected: '251733189', found: '251743666'