QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799957#1189. Wall PaintingSFlyerAC ✓442ms101376kbC++142.4kb2024-12-05 19:46:462024-12-05 19:46:48

Judging History

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

  • [2024-12-05 19:46:48]
  • 评测
  • 测评结果:AC
  • 用时:442ms
  • 内存:101376kb
  • [2024-12-05 19:46:46]
  • 提交

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'