QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#174595 | #6606. The Boomsday Project | LFCode | AC ✓ | 580ms | 59456kb | C++14 | 1.4kb | 2023-09-10 10:41:40 | 2023-09-10 10:41:41 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#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 infor{int p,q;}d[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++){d[i].p=read();d[i].q=read();}
std::sort(d+1,d+m+1,[&](infor x,infor y){return x.p<y.p;});
for(int i=1;i<=m;i++)
for(int j=1;j<=d[i].q;j++)a[++tot]=d[i].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]);
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9704kb
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: 0ms
memory: 9732kb
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: 534ms
memory: 58464kb
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: 559ms
memory: 57792kb
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: 501ms
memory: 53316kb
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: 0
Accepted
time: 554ms
memory: 59456kb
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:
300840
result:
ok 1 number(s): "300840"
Test #7:
score: 0
Accepted
time: 501ms
memory: 56936kb
input:
500 100 1000 39 154 45298 34 357 85100 46 557 748764 24 896 665708 97 28 1885 42 668 1223574 53 614 669616 28 648 1145794 28 649 1208449 93 689 1227367 56 772 163614 54 468 462959 28 400 721934 25 391 208246 55 388 473486 67 106 55488 63 10 18506 6 113 191992 43 100 165666 29 952 1200973 79 519 5596...
output:
1147818
result:
ok 1 number(s): "1147818"
Test #8:
score: 0
Accepted
time: 531ms
memory: 58600kb
input:
500 100 1000 25 155 54027 94 392 88410 71 600 1051186 31 391 104487 28 851 1539952 37 30 20168 26 722 164500 79 802 967771 68 481 152325 53 46 19203 91 445 398966 98 418 250634 96 387 128328 3 439 679797 13 201 81420 7 10 2504 75 139 213047 19 289 499368 1 100 44418 67 834 737897 87 235 57104 76 943...
output:
42900
result:
ok 1 number(s): "42900"
Test #9:
score: 0
Accepted
time: 460ms
memory: 53580kb
input:
500 100 1000 51 42 16628 43 190 172609 19 71 111541 5 307 90084 24 370 464785 40 728 4358 70 289 140870 12 834 1379849 1 832 380970 57 788 14539 99 217 116555 22 293 75003 64 508 504262 76 757 745132 82 508 111516 48 447 728589 94 91 128698 34 689 724690 55 206 140536 19 6 11110 54 148 284655 82 577...
output:
441300
result:
ok 1 number(s): "441300"
Test #10:
score: 0
Accepted
time: 512ms
memory: 56804kb
input:
500 100 1000 34 971 1557997 38 468 536953 16 133 88701 46 139 79800 35 5 2908 43 991 771999 55 595 439720 10 1 1409 20 235 373255 72 178 218511 67 164 252433 70 155 22009 46 838 1434022 29 13 16155 43 694 721903 1 142 134637 10 206 232264 79 235 138874 91 964 1840417 46 379 36314 91 541 105296 82 74...
output:
3846908
result:
ok 1 number(s): "3846908"
Test #11:
score: 0
Accepted
time: 555ms
memory: 59264kb
input:
500 100 1000 78 680 93658 91 681 935976 27 885 1219969 74 426 233941 88 143 257524 55 743 1279359 4 841 807430 52 61 58591 37 515 992872 67 440 525617 37 119 4821 96 164 47048 53 98 41919 46 451 804734 71 440 377656 45 988 1339930 79 983 1954579 14 16 8209 45 496 165715 46 391 163844 64 334 585656 3...
output:
147840
result:
ok 1 number(s): "147840"
Test #12:
score: 0
Accepted
time: 554ms
memory: 58800kb
input:
500 100 1000 17 337 520830 13 320 435598 34 344 332171 1 779 442379 32 280 282 55 615 1050064 55 55 101465 49 434 119384 33 728 285107 37 378 345293 4 575 419615 18 929 254491 10 82 30957 57 704 240496 55 39 9470 63 193 273163 27 208 298983 45 721 493246 20 427 255468 76 733 1062484 91 514 670590 1 ...
output:
300330
result:
ok 1 number(s): "300330"
Test #13:
score: 0
Accepted
time: 543ms
memory: 55488kb
input:
500 100 500000 88 337 305883611 41 175 37057752 49 55 39547475 40 419 77409822 53 926 95898196 88 305 282306241 64 472 150142072 67 722 627918523 64 734 45315633 97 396 275395403 67 341 286394272 1 808 40798374 54 763 4529294 30 206 157558711 72 937 593507461 39 967 634291057 73 279 193814503 22 166...
output:
7958679
result:
ok 1 number(s): "7958679"
Test #14:
score: 0
Accepted
time: 535ms
memory: 57760kb
input:
500 100 500000 48 291 77324210 55 803 201189051 80 613 86857684 37 295 209966905 19 973 81478590 86 601 110983393 66 964 291658381 60 112 77757355 61 846 15731458 86 235 168473182 89 136 14994111 92 540 92431585 59 215 134606352 89 575 9269688 71 22 15341815 38 50 17724764 37 792 70648577 37 619 228...
output:
79212560
result:
ok 1 number(s): "79212560"
Test #15:
score: 0
Accepted
time: 556ms
memory: 58104kb
input:
500 100 500000 64 664 92524273 95 898 890754323 1 352 158420593 49 259 36712015 53 685 114613304 72 430 68130085 59 673 410775795 52 953 252202681 91 19 15952819 34 1 682089 1 683 485683885 89 122 22249286 3 331 280433737 28 805 54297100 75 206 198492355 35 353 152254081 55 515 426325231 18 600 2379...
output:
114964628
result:
ok 1 number(s): "114964628"
Test #16:
score: 0
Accepted
time: 515ms
memory: 57884kb
input:
500 100 500000 5 706 80771411 89 292 46009981 82 685 198826346 34 76 18282733 34 912 53442973 37 459 58657141 86 618 162695850 26 291 256158377 97 676 342326785 25 200 9186714 12 301 21336363 73 966 257245547 58 913 68981482 37 325 17384036 97 691 68915352 43 263 14894675 97 744 220748347 59 265 117...
output:
132025996
result:
ok 1 number(s): "132025996"
Test #17:
score: 0
Accepted
time: 542ms
memory: 58836kb
input:
500 100 500000 72 499 85157330 65 668 402065169 76 631 136078671 34 259 52726521 19 21 1526977 93 25 13513520 49 83 14052025 16 114 54732239 12 460 263225401 89 253 39225643 74 229 132679456 99 760 340672861 1 722 225419801 82 35 6430447 10 23 18130531 62 279 161129003 91 226 203120137 17 783 263011...
output:
30194785
result:
ok 1 number(s): "30194785"
Test #18:
score: 0
Accepted
time: 518ms
memory: 56964kb
input:
500 100 500000 14 865 3462216 81 815 302995417 73 535 473631124 67 786 468787159 91 224 109097456 85 139 48202412 43 782 33553936 58 933 39518707 30 502 257510839 1 809 78008815 82 377 267465561 45 413 28023932 6 176 109303043 24 178 121890167 43 964 672867649 28 530 52807595 88 656 72050224 19 184 ...
output:
139452477
result:
ok 1 number(s): "139452477"
Test #19:
score: 0
Accepted
time: 552ms
memory: 58276kb
input:
500 100 500000 91 157 90000268 85 202 65400524 19 87 65854317 2 784 199206406 31 385 71919388 44 454 228454078 62 27 26221013 40 772 136004980 98 547 451215803 63 693 56256549 25 349 29986924 19 17 12496438 49 859 25962715 82 802 41624289 19 381 153612451 17 109 70823152 45 671 163997107 49 201 1408...
output:
9589965
result:
ok 1 number(s): "9589965"
Test #20:
score: 0
Accepted
time: 516ms
memory: 57968kb
input:
500 100 500000 98 328 294265795 46 730 467761075 25 10 8963806 46 10 4897491 23 470 240258529 74 679 312776671 82 963 12205175 67 418 59720525 1 379 51929221 46 261 152905862 62 767 517344334 27 397 208108235 15 912 194493590 59 135 127130395 55 877 13946562 15 524 403763035 44 301 22555681 73 616 2...
output:
18704981
result:
ok 1 number(s): "18704981"
Test #21:
score: 0
Accepted
time: 548ms
memory: 59324kb
input:
500 100 500000 70 28 12290551 98 374 365080617 39 808 120996209 10 478 14058145 55 586 207845662 24 77 56748997 18 797 311534209 87 662 55884169 88 892 380907793 7 757 137316691 43 289 26295795 34 641 56952169 72 400 6307945 43 925 520243276 23 604 390825282 1 985 10709969 24 832 56014037 5 595 2152...
output:
114734046
result:
ok 1 number(s): "114734046"
Test #22:
score: 0
Accepted
time: 517ms
memory: 55444kb
input:
500 100 500000 33 787 18617873 69 96 3342361 45 772 99254378 97 37 33415789 68 401 342282709 35 535 107981309 96 752 15176305 46 175 46186691 13 678 62106220 14 574 428383473 28 579 12765311 27 782 411868535 78 555 332689237 7 567 11369695 40 151 78401699 15 61 40150307 38 621 31517175 73 385 850029...
output:
39127150
result:
ok 1 number(s): "39127150"
Test #23:
score: 0
Accepted
time: 536ms
memory: 57424kb
input:
500 2 1000 1 20 20892 1 627 55354 1 747 1404314 1 676 597007 1 814 1569851 1 397 691575 1 4 4575 1 382 624404 1 197 201850 1 799 643576 1 895 1510533 1 800 552439 1 954 1149851 1 892 676406 1 882 1348956 1 318 324094 1 238 439111 1 397 471003 1 119 130686 1 637 77731 1 292 35234 1 243 348565 1 332 2...
output:
453596
result:
ok 1 number(s): "453596"
Test #24:
score: 0
Accepted
time: 426ms
memory: 47856kb
input:
500 2 1000 1 525 987507 1 92 28315 1 655 631455 1 42 27847 1 3 2031 1 886 1541395 1 616 903748 1 140 259414 1 870 359120 1 502 419577 1 700 133293 1 899 440910 1 568 920335 1 108 166882 1 865 557725 1 829 1076839 1 417 141389 1 190 365986 1 652 67148 1 437 135833 1 720 634181 1 437 464374 1 253 1253...
output:
558545
result:
ok 1 number(s): "558545"
Test #25:
score: 0
Accepted
time: 518ms
memory: 56892kb
input:
500 2 1000 1 230 313202 1 841 786856 1 562 1106407 1 118 221149 1 607 135212 1 142 275635 1 361 177717 1 967 325151 1 847 116256 1 7 3899 1 937 1571908 1 424 29177 1 452 507919 1 781 1255985 1 664 420150 1 134 180586 1 738 961612 1 246 471837 1 781 1211881 1 904 1147376 1 161 6584 1 832 1098686 1 56...
output:
2524566
result:
ok 1 number(s): "2524566"
Test #26:
score: 0
Accepted
time: 560ms
memory: 57732kb
input:
500 2 1000 1 256 471450 1 520 914190 1 217 129973 1 578 288473 1 66 57103 1 479 579870 1 135 30821 1 328 400054 1 930 1625351 1 834 912799 1 712 698720 1 200 289942 1 154 4613 1 193 282323 1 635 686599 1 817 1143189 1 482 659647 1 2 3613 1 798 155016 1 450 542961 1 256 480685 1 298 264533 1 648 1287...
output:
1161132
result:
ok 1 number(s): "1161132"
Test #27:
score: 0
Accepted
time: 459ms
memory: 51604kb
input:
500 2 1000 1 778 935019 1 778 1279930 1 489 385890 1 166 20905 1 544 296080 1 537 104811 1 205 136906 1 126 25221 1 97 181203 1 358 235607 1 230 420859 1 452 103675 1 614 1206685 1 487 336880 1 81 105199 1 203 239566 1 751 1501191 1 16 22750 1 478 731853 1 116 98816 1 501 822721 1 402 129998 1 171 2...
output:
2048000
result:
ok 1 number(s): "2048000"
Test #28:
score: 0
Accepted
time: 484ms
memory: 54100kb
input:
500 2 1000 1 43 5541 1 145 178512 1 568 797703 1 676 1156399 1 48 20556 1 666 1084477 1 613 874562 1 115 229222 1 838 12776 1 37 4240 1 433 232770 1 149 208649 1 859 1502448 1 823 607270 1 557 209887 1 30 8917 1 946 1515935 1 181 108501 1 610 14281 1 649 71934 1 570 574552 1 679 735423 1 250 421609 ...
output:
1532601
result:
ok 1 number(s): "1532601"
Test #29:
score: 0
Accepted
time: 544ms
memory: 58836kb
input:
500 2 1000 1 76 132414 1 805 983406 1 539 476698 1 20 14980 1 455 426628 1 865 526788 1 719 1371458 1 235 74353 1 563 650067 1 928 334812 1 62 20656 1 403 212518 1 790 232018 1 227 10492 1 88 130360 1 811 1402221 1 656 1234662 1 372 413162 1 217 416241 1 463 248133 1 601 826995 1 196 367471 1 208 18...
output:
435918
result:
ok 1 number(s): "435918"
Test #30:
score: 0
Accepted
time: 468ms
memory: 48948kb
input:
500 2 1000 1 685 462336 1 847 1525819 1 835 86362 1 978 1764196 1 856 446571 1 34 12986 1 596 194319 1 229 38276 1 343 492923 1 470 526324 1 112 180187 1 239 172474 1 213 417967 1 778 929237 1 108 55355 1 861 1682258 1 190 131428 1 312 72644 1 689 112893 1 811 847337 1 179 51582 1 886 51309 1 571 94...
output:
3685
result:
ok 1 number(s): "3685"
Test #31:
score: 0
Accepted
time: 558ms
memory: 55532kb
input:
500 2 1000 1 312 307329 1 508 164968 1 781 760215 1 811 1028641 1 487 300192 1 610 178976 1 376 179339 1 544 500087 1 298 30710 1 105 183890 1 732 614311 1 943 195290 1 756 222465 1 149 99864 1 100 179632 1 662 1239639 1 808 777874 1 622 256185 1 177 189343 1 17 19480 1 772 1092661 1 552 263508 1 95...
output:
15540
result:
ok 1 number(s): "15540"
Test #32:
score: 0
Accepted
time: 462ms
memory: 50140kb
input:
500 2 1000 1 46 19203 1 445 398966 1 418 250634 1 387 128328 1 439 679797 1 201 81420 1 10 2504 1 139 213047 1 289 499368 1 100 44418 1 834 737897 1 235 57104 1 943 750995 1 633 602973 1 566 1130728 1 562 119948 1 508 315452 1 103 20053 1 538 560044 1 325 189210 1 552 911298 1 833 784630 1 808 39318...
output:
35805
result:
ok 1 number(s): "35805"
Test #33:
score: 0
Accepted
time: 570ms
memory: 59008kb
input:
500 100 1000 67 290 476380 21 703 1028496 35 52 100444 88 523 617114 1 607 1046903 36 451 529682 23 658 612301 42 636 307280 67 313 316282 1 666 1154728 13 621 992262 10 880 493415 22 966 661359 65 42 74641 37 173 114865 12 951 1335991 19 384 579204 65 822 1047603 35 670 610295 73 949 1741869 77 425...
output:
105266
result:
ok 1 number(s): "105266"
Test #34:
score: 0
Accepted
time: 573ms
memory: 59392kb
input:
500 100 1000 36 847 997029 14 105 115679 88 136 72762 43 625 157018 67 358 670807 33 100 81046 52 475 908223 30 838 1008427 51 437 452642 6 199 312095 13 952 1639911 1 299 435462 55 60 50191 11 184 26738 56 661 451988 78 577 712189 31 466 281355 19 68 59770 20 295 303023 53 795 579036 99 276 476229 ...
output:
654278
result:
ok 1 number(s): "654278"
Test #35:
score: 0
Accepted
time: 580ms
memory: 58688kb
input:
500 100 1000 54 625 1176830 67 667 891221 19 649 882303 10 953 347848 85 422 826426 73 226 430994 52 442 172740 37 253 44898 3 367 188588 78 925 871687 94 371 100338 94 892 1567637 58 442 215603 7 400 398228 63 808 910528 34 784 1285061 34 931 630666 28 932 694032 49 770 898348 68 780 1265032 45 675...
output:
1281818
result:
ok 1 number(s): "1281818"
Test #36:
score: 0
Accepted
time: 574ms
memory: 58000kb
input:
500 100 1000 92 844 148312 7 1 331 73 971 1313630 22 75 66791 5 61 97004 40 326 132738 5 659 1243375 88 906 205770 52 775 1279807 82 297 62915 26 829 769023 7 445 501221 62 580 279152 19 450 552715 10 196 339466 73 347 310575 87 817 1515287 10 870 658748 94 223 159800 70 628 1133106 49 402 322757 1 ...
output:
778686
result:
ok 1 number(s): "778686"
Test #37:
score: 0
Accepted
time: 566ms
memory: 58856kb
input:
500 100 1000 8 858 661319 51 856 1225919 88 991 1773217 58 544 67262 46 872 762745 1 585 718382 88 473 603352 72 538 38086 82 88 98511 91 574 669102 86 460 113695 94 76 30905 91 766 65331 23 90 1407 63 793 1058043 54 501 435092 78 124 165724 89 820 470094 14 543 265785 7 42 56392 92 281 445207 94 73...
output:
1148100
result:
ok 1 number(s): "1148100"
Test #38:
score: 0
Accepted
time: 559ms
memory: 58084kb
input:
500 100 1000 46 398 214401 66 13 11649 16 208 278202 55 919 437458 52 427 206159 91 1 1398 43 712 1222487 95 313 288700 63 823 530183 98 622 335528 97 40 20305 78 375 90921 88 400 619661 23 760 164056 67 893 75575 19 238 333532 82 75 121680 56 728 906488 78 574 661090 1 72 124933 28 369 233557 45 27...
output:
585162
result:
ok 1 number(s): "585162"
Test #39:
score: 0
Accepted
time: 547ms
memory: 59252kb
input:
500 100 1000 28 82 27918 97 38 71575 33 447 613081 58 106 145948 15 90 11638 42 435 491932 67 951 860179 40 875 1300012 73 238 320814 36 610 456476 75 685 1138693 66 560 1063305 97 732 610074 76 493 749034 98 587 170089 16 122 102520 77 934 131474 68 988 1963249 91 974 1376482 41 514 1015618 49 887 ...
output:
349585
result:
ok 1 number(s): "349585"
Test #40:
score: 0
Accepted
time: 578ms
memory: 59324kb
input:
500 100 1000 13 864 1021861 66 438 340932 88 523 740761 67 304 412399 22 362 618320 13 139 11324 85 800 1459895 40 846 166122 55 278 327871 23 727 373451 71 190 25658 53 829 1354424 58 835 236118 38 70 109484 23 993 1902936 36 74 128761 44 293 227107 34 213 275915 52 827 926571 26 632 512397 46 562 ...
output:
783729
result:
ok 1 number(s): "783729"
Test #41:
score: 0
Accepted
time: 577ms
memory: 58344kb
input:
500 100 1000 82 383 456209 33 50 73618 43 498 603477 14 519 478847 82 274 372261 67 935 263995 4 242 363360 71 52 14081 67 253 117060 52 667 100441 55 686 1159363 1 667 1112915 97 573 475471 78 523 763196 52 235 254328 47 619 315134 67 38 2899 52 678 584314 60 739 994297 27 505 709552 85 610 387289 ...
output:
6249161
result:
ok 1 number(s): "6249161"
Test #42:
score: 0
Accepted
time: 558ms
memory: 58100kb
input:
500 100 1000 50 930 647471 14 125 161506 90 406 798912 71 783 59753 82 277 529357 22 383 178599 56 305 535533 56 427 528894 89 226 134635 76 25 36022 96 812 148411 11 331 119739 47 64 63172 80 761 1388404 37 57 37236 89 622 808403 88 787 260082 12 724 893995 87 337 604141 43 438 43386 45 455 42754 9...
output:
2159944
result:
ok 1 number(s): "2159944"