QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#174593#6606. The Boomsday ProjectLFCodeWA 525ms55120kbC++141.3kb2023-09-10 10:35:042023-09-10 10:35:05

Judging History

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

  • [2023-09-10 10:35:05]
  • 评测
  • 测评结果:WA
  • 用时:525ms
  • 内存:55120kb
  • [2023-09-10 10:35:04]
  • 提交

answer

#include<cstdio>
#define lg(x) (31-__builtin_clz(x))
#define llg(x) (63-__builtin_clzll(x))
#define int long long
const int N=300086,INF=1e18+7;
int n,m,r,tot,a[N],np[N],f[N];
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
struct cinf{int d,k,c,mn;}c[N];
struct STList{
	int sze,a[N][20];
	STList(){sze=0;}
	bool push(int x){
		a[++sze][0]=x;
		for(int i=1;(1<<i)<=sze;i++)
			a[sze][i]=Min(a[sze][i-1],a[sze-(1<<(i-1))][i-1]);
		return true;
	}
	int query(int l,int r){
		if(l>r)return INF;if(l<1)return 0;if(r>sze)r=sze;int lo=llg(r-l+1);
		return Min(a[r][lo],a[l+(1<<lo)-1][lo]);
	}
}rmq;
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
signed main(){
	n=read();m=read();r=read();
	for(int i=1;i<=n;i++){c[i].d=read();c[i].k=read();c[i].c=read();np[i]=1;}
	for(int i=1;i<=m;i++){
		int p=read();int q=read();
		for(int j=1;j<=q;j++)a[++tot]=p;
	}
	for(int i=1;i<=tot;i++){
		f[i]=f[i-1]+r;
		for(int j=1;j<=n;j++){
			int pos=i-c[j].k+1;pos=Max(pos,1);
			while(a[np[j]]<a[i]-c[j].d+1)np[j]++;
			pos=Max(np[j],pos);
			f[i]=Min(f[i],rmq.query(pos-1,i-1)+c[j].c);
		}
		rmq.push(f[i]);
	}
	printf("%lld",f[tot]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 1 10
1 3 12
1 2 9
1 10

output:

42

result:

ok 1 number(s): "42"

Test #2:

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

input:

2 4 10
1 3 12
1 2 9
1 3
2 3
3 3
4 1

output:

45

result:

ok 1 number(s): "45"

Test #3:

score: 0
Accepted
time: 511ms
memory: 54844kb

input:

500 100 1000
95 20 20892
73 627 55354
52 747 1404314
19 676 597007
65 814 1569851
91 397 691575
81 4 4575
97 382 624404
21 197 201850
67 799 643576
27 895 1510533
3 800 552439
49 954 1149851
70 892 676406
82 882 1348956
1 318 324094
43 238 439111
94 397 471003
16 119 130686
1 637 77731
79 292 35234
...

output:

450790

result:

ok 1 number(s): "450790"

Test #4:

score: 0
Accepted
time: 525ms
memory: 54904kb

input:

500 100 1000
8 910 1405086
65 931 697221
73 534 1051699
74 13 7497
64 631 991592
79 481 511568
92 892 477132
91 588 842013
21 389 750794
19 955 1333270
85 889 1334457
46 295 505372
83 486 449366
67 67 119659
82 446 408487
25 736 319997
31 889 23280
1 41 74813
93 928 1189573
88 468 455471
7 10 18865
...

output:

3276270

result:

ok 1 number(s): "3276270"

Test #5:

score: 0
Accepted
time: 474ms
memory: 53652kb

input:

500 100 1000
35 122 153490
71 121 27207
73 967 409546
88 325 182835
37 602 533155
61 546 114146
70 359 251186
64 429 591088
63 445 428802
81 819 408704
49 364 244867
64 937 1422956
98 505 713891
1 454 61697
91 673 116038
89 463 123737
67 724 1061372
31 1 1838
73 127 173419
72 122 8068
55 928 65539
3...

output:

762564

result:

ok 1 number(s): "762564"

Test #6:

score: -100
Wrong Answer
time: 515ms
memory: 55120kb

input:

500 100 1000
77 590 825100
67 901 1633566
29 703 886708
86 223 168970
6 676 1162365
46 669 1308904
73 96 125961
37 529 774376
79 741 516927
95 835 602321
25 208 384673
16 20 12510
41 226 164928
68 836 1412302
52 689 418717
40 481 789905
10 838 220638
35 846 885451
54 736 1470524
13 490 224433
12 354...

output:

301385

result:

wrong answer 1st numbers differ - expected: '300840', found: '301385'