QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799957 | #1189. Wall Painting | SFlyer | AC ✓ | 442ms | 101376kb | C++14 | 2.4kb | 2024-12-05 19:46:46 | 2024-12-05 19:46:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4e5+5;
struct segt{
ll t[N<<2];
void pu(int k){
t[k]=max(t[k<<1],t[k<<1|1]);
}
void bd(int k,int l,int r){
t[k]=-1e18;
if (!l) t[k]=0;
if (l==r) return;
int mid=l+r>>1;
bd(k<<1,l,mid);
bd(k<<1|1,mid+1,r);
pu(k);
}
void upd(int k,int l,int r,int p,ll v){
if(l==r){
t[k]=max(t[k],v);
return;
}
int mid=l+r>>1;
if (p<=mid) upd(k<<1,l,mid,p,v);
else upd(k<<1|1,mid+1,r,p,v);
pu(k);
}
ll qy(int k,int l,int r,int ql,int qr){
if (ql<=l && r<=qr) return t[k];
if (r<ql || l>qr) return -1e18;
int mid=l+r>>1;
return max(qy(k<<1,l,mid,ql,qr),qy(k<<1|1,mid+1,r,ql,qr));
}
} t1[3],t2[3],t3[3];
ll n,m,X,Y;
struct node {
int l,r,c;
} a[N];
bool cmp(node x,node y){
return x.l<y.l;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>X>>Y;
vector<int> v;
for (int i=1; i<=m; i++){
cin>>a[i].c>>a[i].l>>a[i].r;
v.push_back(a[i].l);
v.push_back(a[i].r);
a[i].c--;
}
sort(a+1,a+1+m,cmp);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for (int i=1; i<=m; i++){
a[i].l=lower_bound(v.begin(),v.end(),a[i].l)-v.begin()+1;
a[i].r=lower_bound(v.begin(),v.end(),a[i].r)-v.begin()+1;
}
int cnt=v.size();
#define al 1,0,cnt
for (int i=0; i<3; i++){
t1[i].bd(al);
t2[i].bd(al);
t3[i].bd(al);
}
ll ans=-1e18;
for (int i=1; i<=m; i++){
int l=a[i].l;
int r=a[i].r;
int c=a[i].c;
ll tmp=-1e18;
for (int j=0; j<3; j++){
if (j==c){
tmp=max({tmp,t1[j].qy(al,0,l-1)+X*(v[r-1]-v[l-1]+1),t2[j].qy(al,l,r-1)+X*v[r-1]});
}
else{
tmp=max({tmp,t1[j].qy(al,0,l-1)+X*(v[r-1]-v[l-1]+1),t3[j].qy(al,l,r-1)+(X+Y)*(v[l-1]-1)+X*v[r-1]});
}
}
ans=max(ans,tmp);
t1[c].upd(al,r,tmp);
t2[c].upd(al,r,tmp-X*v[r-1]);
t3[c].upd(al,r,tmp-(X+X+Y)*v[r-1]);
}
cout<<ans<<"\n";
return 0;
}
// TRY! TRY! TRY!
/*
Think twice before coding. Have you overkilled?
Think twice before submitting.
Check on the samples and constraints carefully.
*/
/*
Be brave to guess.
Is your former/first approach correct?
Follow your intuition.
Use a notebook to note down your ideas and check whether they are correct.
*/
/*
A simple brute force may work? There is some limit on the answer?
Try to find patterns.
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 22292kb
input:
8 5 10 5 1 1 7 3 1 2 1 5 6 3 1 4 3 6 8
output:
70
result:
ok answer is '70'
Test #2:
score: 0
Accepted
time: 0ms
memory: 22252kb
input:
26 3 9 7 1 11 13 3 1 11 3 18 26
output:
182
result:
ok answer is '182'
Test #3:
score: 0
Accepted
time: 0ms
memory: 22028kb
input:
21 10 10 5 1 10 21 3 4 16 1 1 7 3 11 21 3 1 16 3 3 3 2 1 17 3 5 18 1 7 11 2 3 14
output:
210
result:
ok answer is '210'
Test #4:
score: 0
Accepted
time: 0ms
memory: 22088kb
input:
21 15 8 7 2 12 21 2 1 2 3 6 13 2 13 17 1 11 19 3 3 5 1 12 13 3 2 2 1 12 15 1 5 17 1 2 3 1 1 9 1 8 12 3 8 9 3 2 9
output:
153
result:
ok answer is '153'
Test #5:
score: 0
Accepted
time: 0ms
memory: 22028kb
input:
8 5 36426 79445 3 6 8 3 1 2 3 1 4 1 1 7 1 5 6
output:
254982
result:
ok answer is '254982'
Test #6:
score: 0
Accepted
time: 0ms
memory: 22028kb
input:
5 8 29211 39679 1 5 5 1 3 4 2 3 4 3 3 5 1 1 5 1 1 5 3 2 5 3 1 5
output:
146055
result:
ok answer is '146055'
Test #7:
score: 0
Accepted
time: 0ms
memory: 22132kb
input:
14 4 95138 64223 2 11 12 2 2 11 2 8 13 3 8 14
output:
1141656
result:
ok answer is '1141656'
Test #8:
score: 0
Accepted
time: 2ms
memory: 22332kb
input:
19 9 70607 66466 3 8 9 2 5 10 2 16 18 2 4 18 3 1 4 3 9 10 2 10 15 2 4 14 3 1 3
output:
1270926
result:
ok answer is '1270926'
Test #9:
score: 0
Accepted
time: 0ms
memory: 22088kb
input:
11 8 45559 56553 3 2 5 2 3 8 2 3 9 1 1 7 1 5 11 2 3 8 1 7 11 1 1 4
output:
501149
result:
ok answer is '501149'
Test #10:
score: 0
Accepted
time: 4ms
memory: 24484kb
input:
861607398 3876 81011 49233 3 394669701 515805550 3 88996129 148083649 3 522857002 746888599 2 645596889 805867588 3 30238644 820298182 3 8253822 719679027 1 121050605 803152099 1 511310692 691678587 3 41691669 810609226 3 125849609 390382629 2 91619093 835765994 3 113524757 737106256 1 579522464 794...
output:
69780783122315
result:
ok answer is '69780783122315'
Test #11:
score: 0
Accepted
time: 0ms
memory: 22312kb
input:
896934802 2034 78594 45986 3 665099576 755325239 1 690853403 798399811 1 17080562 526231895 3 312009108 649372827 2 489917735 808418997 3 359391689 514546180 1 189527519 760519296 2 178800174 605822714 2 60073436 791079028 3 246127878 879611791 3 196052921 435825883 3 57641794 593028109 3 356892606 ...
output:
70444038175598
result:
ok answer is '70444038175598'
Test #12:
score: 0
Accepted
time: 7ms
memory: 22140kb
input:
912204693 3694 3312 65674 3 80437219 436613274 1 610848541 727022084 3 1750656 868066556 2 659836901 671813159 1 111587895 817844288 3 347786139 729671977 2 403671550 686449322 3 323146779 815200702 1 17454721 113054903 2 11523679 755677199 1 2645527 696319635 2 628659063 819385142 3 416417701 57177...
output:
3019806997200
result:
ok answer is '3019806997200'
Test #13:
score: 0
Accepted
time: 6ms
memory: 22340kb
input:
892914760 2605 93081 15036 3 495002074 583693802 1 298560052 775173526 2 122987644 859304341 2 243604777 702957537 3 381396260 666594805 3 30994112 273169685 1 75408992 489157472 1 225154568 861138176 3 385052596 732125476 1 689715959 799906489 1 79966736 754906506 1 328098587 850664778 1 233669059 ...
output:
83061874253415
result:
ok answer is '83061874253415'
Test #14:
score: 0
Accepted
time: 8ms
memory: 24484kb
input:
978990663 3917 87157 52580 3 301092152 521087727 3 74798056 363257465 1 126873203 482426534 1 234370329 450147031 3 146984025 512140022 2 198178069 211011402 3 486239321 608355542 2 50845738 354771546 1 669727182 919675114 1 173675604 875419545 3 16215570 639661710 3 176123545 338581600 3 194465713 ...
output:
85316484626163
result:
ok answer is '85316484626163'
Test #15:
score: 0
Accepted
time: 442ms
memory: 99772kb
input:
1000000000 200000 55092 83810 2 236807806 596437313 2 299081053 388998255 1 537527962 852090755 1 119242695 844067216 3 21199942 138488139 2 183323115 793284808 1 674587283 702383298 3 868116272 996078128 1 171309035 799448314 3 392165036 885697997 3 581957279 733296335 1 110875672 722696889 3 15429...
output:
55091839737372
result:
ok answer is '55091839737372'
Test #16:
score: 0
Accepted
time: 400ms
memory: 99356kb
input:
975561632 185015 74652 95607 2 261359243 522821889 2 521524832 534718048 2 69258706 726609734 3 365313218 941831128 1 468614694 494718089 3 453926520 767002495 1 430724408 742840270 2 613563155 914747429 3 7225116 571065929 2 56869922 310849052 1 201250431 840203184 3 632128491 724653607 3 574192642...
output:
72827395456212
result:
ok answer is '72827395456212'
Test #17:
score: 0
Accepted
time: 396ms
memory: 100508kb
input:
860444325 195859 10598 37344 1 29358334 257677819 2 8718539 117791682 1 411165181 518220029 1 119369681 681236149 3 39891876 632599031 1 4595621 180634475 3 268888871 321977284 3 14282197 231406835 2 62757831 110105466 1 100228795 276387225 1 718036421 800557211 1 486821443 814745051 3 90726132 6194...
output:
9118918871776
result:
ok answer is '9118918871776'
Test #18:
score: 0
Accepted
time: 395ms
memory: 100076kb
input:
879363156 186260 27854 16442 1 227602645 571700701 1 289654740 666075191 3 350156458 484007457 2 125383841 676881335 1 620850306 621538241 2 620561989 649627421 3 31725459 288982240 3 126828011 704152831 1 187742245 600644565 2 507846399 593329192 3 76571788 230303537 1 162846378 239455107 3 2000167...
output:
24493727226902
result:
ok answer is '24493727226902'
Test #19:
score: 0
Accepted
time: 417ms
memory: 100468kb
input:
956539429 197137 14354 72878 2 537137001 796901491 1 266394970 706764143 1 496792763 650470113 1 323503129 742869719 2 357182317 833973330 2 206118767 724378441 1 5543478 168374904 2 23352290 926276561 3 110658640 591722501 1 315841423 874343969 3 214142081 302918126 2 376180053 643749299 2 35988399...
output:
13730151346714
result:
ok answer is '13730151346714'
Test #20:
score: 0
Accepted
time: 411ms
memory: 100688kb
input:
877591547 190142 55482 62801 1 556903120 787496666 3 30554202 678678526 1 186343496 525527237 1 204949104 713201610 3 278777068 641044340 3 150487256 859763751 1 235218915 409369566 3 638756157 716855413 1 285992779 433990574 1 144846398 225006058 1 38681102 671735928 1 408694691 728083656 3 6791987...
output:
48690178792962
result:
ok answer is '48690178792962'
Test #21:
score: 0
Accepted
time: 394ms
memory: 99720kb
input:
844166199 191759 25223 19232 1 523295872 798049924 3 470938890 726342073 3 94219190 173681907 3 497186387 507241826 1 409940943 546643036 1 260712566 374920306 1 709424532 728636163 1 72921839 792695483 2 587631686 773321027 2 17339616 515866321 1 586243096 615895332 3 338491605 595842311 1 48997322...
output:
21292366833452
result:
ok answer is '21292366833452'
Test #22:
score: 0
Accepted
time: 406ms
memory: 99500kb
input:
811469323 192725 50654 99930 1 136622412 434749220 2 235847684 359055691 2 92247131 729009594 3 336121599 368733343 3 111005226 221532901 1 22120802 278468850 2 355885957 568480332 3 186601254 714643820 2 359786281 450052704 1 16775797 684583771 2 248169177 685572262 1 196808791 281079464 2 26261107...
output:
41103896797498
result:
ok answer is '41103896797498'
Test #23:
score: 0
Accepted
time: 421ms
memory: 101260kb
input:
898936879 192472 7540 35257 2 725222491 856688276 1 27124640 281176798 3 288794163 873390393 3 295712940 481087572 1 500645579 522552561 1 40632855 507687225 2 350119037 495364260 3 263493751 616010161 1 487631964 655955736 3 378760576 596634569 3 464992776 889424583 3 105082798 591264618 2 19078770...
output:
6777943306420
result:
ok answer is '6777943306420'
Test #24:
score: 0
Accepted
time: 403ms
memory: 99796kb
input:
997796929 187080 32801 82713 2 79368264 265992535 1 437871650 681497601 2 38057366 83370418 1 399342023 552706936 1 418138839 455971458 2 115471523 814000795 3 554089646 680205239 3 681608003 883834838 2 471621948 940888091 3 41180234 138867605 1 327153563 557392282 1 222414681 375469904 1 429987463...
output:
32728655065629
result:
ok answer is '32728655065629'
Test #25:
score: 0
Accepted
time: 411ms
memory: 101080kb
input:
974119337 192391 31516 96081 2 302363828 866756535 3 733712857 869522404 1 38298320 157297945 3 688314528 844764902 3 408740243 874453334 2 671243645 715592546 3 100604346 834764827 2 142000542 667486693 2 254502890 774162554 2 136563436 715288466 2 316065951 581767759 3 45491137 272794654 3 9316254...
output:
30700127564492
result:
ok answer is '30700127564492'
Test #26:
score: 0
Accepted
time: 25ms
memory: 25868kb
input:
1 186204 73862 86488 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 2 1 1 2 1 1 3 1 1 1 1 1 2 1 1 2 1 1 3 1 1 2 1 1 2 1 1 3 1 1 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 3 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 1 1 1 3 1 1 2 1 1 3 1 1 3 1 1 2 1 1 3 1 1 3 1 1 3 1 1 1 1 1 3 1 1 2 1 1 3 1...
output:
73862
result:
ok answer is '73862'
Test #27:
score: 0
Accepted
time: 30ms
memory: 25460kb
input:
3 180456 23981 87623 3 1 3 1 2 2 1 2 3 3 1 3 1 2 3 1 1 1 1 1 2 3 1 1 2 3 3 2 2 2 2 2 2 2 1 1 2 1 1 3 2 3 2 1 1 1 3 3 2 1 2 2 2 2 3 2 3 2 3 3 3 2 3 1 1 2 2 2 3 1 1 3 3 2 3 3 2 2 3 1 2 3 1 2 2 2 3 2 2 3 1 2 3 3 2 2 1 2 2 1 2 2 2 2 3 3 1 2 2 1 1 1 2 3 2 1 3 2 2 3 1 2 3 2 3 3 1 1 2 1 2 2 3 2 3 3 1 2 1 2...
output:
71943
result:
ok answer is '71943'
Test #28:
score: 0
Accepted
time: 49ms
memory: 26796kb
input:
10 181404 83861 98496 3 1 9 3 2 9 3 9 9 2 6 9 1 4 7 3 3 8 2 6 7 1 1 5 2 2 5 2 8 8 2 1 2 3 1 2 2 7 8 1 6 10 1 6 7 2 3 8 1 8 9 3 4 10 2 8 9 3 7 8 1 3 10 2 4 9 3 1 8 3 2 4 2 9 10 2 9 10 3 5 10 2 1 2 2 5 9 1 6 7 1 1 1 1 9 10 1 2 9 2 1 2 3 8 8 2 10 10 1 3 7 3 7 9 3 6 8 2 9 10 1 3 7 1 3 6 2 8 10 2 6 8 3 2...
output:
838610
result:
ok answer is '838610'
Test #29:
score: 0
Accepted
time: 231ms
memory: 100720kb
input:
1000000000 200000 87718 7051 3 362918436 362918535 1 646587150 646587249 2 873957372 873957471 1 860768925 860769024 2 385786372 385786471 3 136344921 136345020 1 817702564 817702663 3 276622236 276622335 1 956223589 956223688 1 812620657 812620756 2 291664000 291664099 3 274460796 274460895 3 37189...
output:
1731498351761
result:
ok answer is '1731498351761'
Test #30:
score: 0
Accepted
time: 238ms
memory: 100116kb
input:
1000000000 200000 63229 64951 1 149409142 149410141 1 898909498 898910497 3 755859439 755860438 1 994387844 994388843 3 133894865 133895864 1 546695869 546696868 1 860084460 860085459 1 303736917 303737916 2 583754115 583755114 3 209490781 209491780 2 643899921 643900920 2 823431063 823432062 2 4008...
output:
11047601992746
result:
ok answer is '11047601992746'
Test #31:
score: 0
Accepted
time: 252ms
memory: 99684kb
input:
1000000000 200000 6073 24856 3 3400150 3410149 2 236710559 236720558 1 574060305 574070304 3 90025905 90035904 2 962544599 962554598 3 423565827 423575826 1 132246969 132256968 2 751272762 751282761 2 741264903 741274902 2 581695470 581705469 1 896284069 896294068 3 275627728 275637727 2 295429250 2...
output:
4788913582805
result:
ok answer is '4788913582805'
Test #32:
score: 0
Accepted
time: 265ms
memory: 99496kb
input:
1000000000 200000 37977 31302 1 543499009 543599008 2 651620834 651720833 1 285618085 285718084 1 254538828 254638827 2 195771938 195871937 1 280379123 280479122 2 521592004 521692003 2 892612937 892712936 2 616053537 616153536 3 268417090 268517089 2 592884073 592984072 2 357306253 357406252 2 2783...
output:
37976912796600
result:
ok answer is '37976912796600'
Test #33:
score: 0
Accepted
time: 274ms
memory: 101376kb
input:
1000000000 200000 78217 20623 2 184170757 185170756 1 300695159 301695158 3 829523017 830523016 2 880967813 881967812 1 523397417 524397416 3 758062351 759062350 2 263247353 264247352 1 161651051 162651050 2 647527178 648527177 2 675926721 676926720 2 187790412 188790411 2 111900658 112900657 1 1711...
output:
78215521933351
result:
ok answer is '78215521933351'
Test #34:
score: 0
Accepted
time: 322ms
memory: 100572kb
input:
1000000000 200000 38125 45113 1 642561857 652561856 2 306398796 316398795 2 918034028 928034027 3 493542967 503542966 2 925134149 935134148 1 799112973 809112972 2 185124233 195124232 2 653635278 663635277 3 613166837 623166836 2 575530260 585530259 3 233215202 243215201 3 358827253 368827252 1 1044...
output:
38124751463125
result:
ok answer is '38124751463125'
Test #35:
score: 0
Accepted
time: 339ms
memory: 100388kb
input:
1000000000 200000 36859 37726 2 812294945 912294944 2 782486326 882486325 3 803347206 903347205 2 410414803 510414802 2 607756981 707756980 3 74071113 174071112 2 91999899 191999898 3 652465578 752465577 1 243927980 343927979 3 303031333 403031332 2 644459863 744459862 1 455969814 555969813 1 193591...
output:
36858707118386
result:
ok answer is '36858707118386'
Test #36:
score: 0
Accepted
time: 42ms
memory: 27008kb
input:
1000000000 200000 98149 39360 3 1 1000000000 1 1 1000000000 2 1 1000000000 2 1 1000000000 3 1 1000000000 1 1 1000000000 1 1 1000000000 1 1 1000000000 2 1 1000000000 2 1 1000000000 2 1 1000000000 2 1 1000000000 1 1 1000000000 1 1 1000000000 1 1 1000000000 3 1 1000000000 2 1 1000000000 3 1 1000000000 ...
output:
98149000000000
result:
ok answer is '98149000000000'
Test #37:
score: 0
Accepted
time: 235ms
memory: 99892kb
input:
1000000000 200000 45728 71688 2 265619837 265620098 3 988064389 988064649 2 60220702 60221254 3 403072240 403072522 1 430987635 430987786 1 801752921 801753640 3 648890560 648891128 2 746141610 746141892 2 782594489 782594621 1 497247063 497247338 2 923306693 923307560 1 330893768 330894695 2 370953...
output:
4679824575920
result:
ok answer is '4679824575920'
Test #38:
score: 0
Accepted
time: 244ms
memory: 100820kb
input:
1000000000 200000 17689 48562 3 585853973 585860368 1 261250565 261252556 2 149666628 149669359 3 285065898 285071908 1 258382747 258387007 2 335702440 335709600 1 344337054 344340964 2 660700704 660702901 1 438968081 438970574 2 570110741 570117112 1 352463993 352469254 3 881849866 881851813 1 8458...
output:
10895683855226
result:
ok answer is '10895683855226'
Test #39:
score: 0
Accepted
time: 274ms
memory: 101016kb
input:
1000000000 200000 24740 2460 2 265829391 265925718 2 249605679 249637656 3 497264589 497308670 3 795202508 795286730 3 854770529 854843304 1 206671960 206708343 1 998538137 998584968 2 906202340 906286736 1 691400097 691475225 1 268584121 268619069 3 56037421 56097787 2 96431691 96462189 1 244355501...
output:
24729255686940
result:
ok answer is '24729255686940'
Test #40:
score: 0
Accepted
time: 285ms
memory: 100308kb
input:
1000000000 200000 86537 47972 3 423502060 423977233 1 431395767 431938499 1 299447594 300090912 1 455428521 455754351 3 680743395 680926540 3 563016342 563562626 2 303856224 304661335 1 84832771 85218917 1 117160402 117795100 1 527213734 527551049 3 769245084 770179091 2 565517971 565687966 3 156272...
output:
86534290872678
result:
ok answer is '86534290872678'
Test #41:
score: 0
Accepted
time: 340ms
memory: 100804kb
input:
1000000000 200000 72869 40648 3 306219135 310984961 2 171006227 172662706 1 230842858 239324693 3 709392405 714899904 1 730542524 732637515 2 297421294 302541744 1 426906515 435794762 2 463976924 472395107 3 699628561 703614819 2 467754670 471454448 1 102965763 110273765 1 653727008 660459773 2 9065...
output:
72868621372676
result:
ok answer is '72868621372676'
Test #42:
score: 0
Accepted
time: 368ms
memory: 100560kb
input:
1000000000 200000 74226 3693 3 693183694 719509007 3 200559016 277402709 2 636366407 711036976 2 383487700 465921998 1 421923666 443001450 1 642669939 717548473 3 46766217 138578418 3 4505774 46290708 2 689395388 773818575 1 447406798 510645832 2 573121700 657505064 1 725731325 779975220 2 347553883...
output:
74225717718522
result:
ok answer is '74225717718522'
Test #43:
score: 0
Accepted
time: 415ms
memory: 99588kb
input:
1000000000 200000 23814 2582 3 156150770 969191269 1 181204978 790531027 3 264213748 799546397 3 225287933 492343146 3 34321738 831739753 1 212003596 743333548 3 671511734 925109251 2 277808672 871812459 1 166548198 684325966 3 275332620 537724682 1 438218659 971633721 3 374530367 647136963 2 116010...
output:
23813988474024
result:
ok answer is '23813988474024'