QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307566#8014. 新本格魔法少女for_to30 382ms48200kbC++141.7kb2024-01-18 20:34:082024-01-18 20:34:08

Judging History

This is the latest submission verdict.

  • [2024-01-18 20:34:08]
  • Judged
  • Verdict: 30
  • Time: 382ms
  • Memory: 48200kb
  • [2024-01-18 20:34:08]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define N 5000005

using namespace std;

int n,m,q;
struct node{
	int opt,l,r,v;
}s[N];
int f[N];

struct segment{
	#define lson k<<1ll
	#define rson lson|1ll
	
	int w[N],tag[N];
	
	void push_up(int k){
		w[k]=w[lson]+w[rson];
	}
	
	void f(int k,int len,int v){
		w[k]=(len*v);
		tag[k]=v;
	}
	
	void push_down(int k,int l,int r){
		if(tag[k]==-1) return;
		
		int mid=(l+r)>>1ll;
		f(lson,mid-l+1,tag[k]);
		f(rson,r-mid,tag[k]);
		tag[k]=-1;
	}
	
	void build(int k,int l,int r){
		tag[k]=-1;
		w[k]=0;
		if(l==r) return;
		
		int mid=(l+r)>>1ll;
		build(lson,l,mid);
		build(rson,mid+1,r);
	}
	
	void update(int k,int l,int r,int nl,int nr,int v){
		if(l>=nl && r<=nr){
			f(k,r-l+1,v);
			return;
		}
		
		push_down(k,l,r);
		int mid=(l+r)>>1ll;
		
		if(mid>=nl) update(lson,l,mid,nl,nr,v);
		if(mid<nr) update(rson,mid+1,r,nl,nr,v);
		push_up(k);
	}
	
	int query(int k,int l,int r,int nl,int nr){
		if(l>=nl && r<=nr) return w[k];
		
		push_down(k,l,r);
		int mid=(l+r)>>1ll,res=0;
		
		if(mid>=nl) res+=query(lson,l,mid,nl,nr);
		if(mid<nr) res+=query(rson,mid+1,r,nl,nr);
		return res;
	}
}t;

signed main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		cin>>s[i].opt;
		
		if(s[i].opt==1) cin>>s[i].l>>s[i].r>>s[i].v;
		else cin>>s[i].l>>s[i].r;
	}
	
	int res=0;
	t.build(1,1,n);
	for(int i=1;i<=m;i++){
		if(s[i].opt==1) t.update(1,1,n,s[i].l,s[i].r,s[i].v);
		else res+=t.query(1,1,n,s[i].l,s[i].r);
		f[i]=res;
	}
	
	int l,r;
	while(q--){
		cin>>l>>r;
		cout<<f[r]<<endl;
	}
	
	return 0;
}

//10 5 4
//1 9 10 7
//1 7 10 9
//2 3 10
//1 10 10 1
//2 5 10
//2 5
//1 1
//3 4
//1 3

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9732kb

input:

100 100 100
2 80 86
2 15 49
1 11 100 25
2 22 36
2 37 100
1 14 16 49
2 74 90
2 28 76
1 43 45 78
1 54 56 27
1 73 75 29
2 34 81
2 51 90
1 13 14 52
1 72 73 2
2 18 58
2 44 58
1 83 85 30
1 86 88 69
1 29 31 25
1 92 94 19
1 48 49 16
1 55 57 91
1 98 100 42
2 13 96
2 50 83
1 23 25 39
1 84 85 55
1 43 45 5
1 90...

output:

24572
52722
53187
53187
33982
24622
24622
53187
15911
28788
28788
35735
17231
3625
22264
24622
47316
15100
35700
44995
52722
51477
45202
24572
52722
51240
51477
39816
52722
48343
39042
51240
51240
51993
52722
13471
49140
51240
22264
52722
19404
24622
7697
49140
51993
52722
51993
35700
51993
17231
49...

result:

wrong answer 1st numbers differ - expected: '8086', found: '24572'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 9672kb

input:

100 100 100
1 56 92 5
1 5 9 91
1 70 92 77
1 45 52 90
1 37 38 36
1 9 10 1
2 1 72
1 79 80 86
2 40 98
1 96 97 89
2 46 78
2 41 58
1 57 58 65
1 73 74 44
1 20 21 54
1 95 96 61
1 23 24 40
1 60 61 48
1 17 18 65
1 43 44 68
1 44 45 7
1 28 29 4
1 10 11 37
1 14 15 44
1 69 70 18
1 33 34 52
1 15 16 67
1 62 63 64
...

output:

6166
14600
14600
14600
6166
6166
14600
14600
6166
14600
14600
0
17551
14600
14600
6166
14600
6166
14600
14600
6166
14600
14600
14600
6166
17551
14600
14600
6166
6166
17551
14600
17551
6166
17551
6166
17551
17551
6166
14600
14600
6166
14600
6166
11554
14600
17551
14600
11554
17551
14600
6166
14600
14...

result:

wrong answer 1st numbers differ - expected: '0', found: '6166'

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 9944kb

input:

5000 5000 5000
1 4070 5000 3145
2 1139 3698
1 798 799 3999
1 2423 2424 2414
1 836 838 518
1 3605 3607 2831
1 525 526 2041
1 4734 4736 1862
2 2408 3821
1 1394 1395 1129
2 601 3026
2 728 4428
1 567 569 4843
2 4235 4835
1 3568 3569 1157
1 3043 3045 4342
1 1813 1815 1888
1 2992 2993 4810
1 1862 1864 112...

output:

1196111834
310946351
2686383758
2686383758
1835161362
106574715
2081398751
2785691385
2214911261
2331329842
2847992605
1781665600
2167122584
2389235370
2470601683
2706629025
310358594
2063841721
2951388739
1527424834
364285310
1744866121
2240785491
2732197080
736511429
422947746
2783547085
213512215...

result:

wrong answer 1st numbers differ - expected: '234959455', found: '1196111834'

Test #4:

score: 0
Wrong Answer
time: 4ms
memory: 9868kb

input:

5000 5000 5000
1 3198 5000 2085
1 2688 2781 3934
1 663 664 1655
1 472 473 4369
1 822 823 75
2 798 2403
1 518 519 4434
1 4022 4023 3962
1 121 122 1996
1 568 569 2710
1 2908 2909 418
1 429 430 4757
1 1361 1362 4590
1 4439 4440 4849
1 3104 3105 2808
1 78 79 1549
1 2111 2112 2281
1 3405 3406 4240
1 2739...

output:

179624885
90886203
258297341
179624885
191732368
33431948
129159811
170279629
167183748
170767034
275652958
122148065
230355293
149051069
71829831
191732368
295425633
135348312
243355898
170767034
191732368
300629685
77995022
63189439
209705964
258297341
135348312
191732368
202764271
276566713
41679...

result:

wrong answer 1st numbers differ - expected: '114655447', found: '179624885'

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 9868kb

input:

4997 5000 4997
1 924 4997 4123
1 1508 1568 759
1 1148 1190 3389
1 908 952 122
1 4976 4997 4100
1 4578 4637 1736
1 2780 2821 3570
1 2830 2874 1796
1 351 391 1
1 762 801 3091
1 2060 2105 398
1 4572 4618 615
1 941 971 853
1 4395 4397 4934
1 4573 4574 4506
1 3697 3698 83
2 112 2024
1 310 311 1941
1 2116...

output:

893906810
1212060250
1071613853
423264937
1149595052
966077712
1018970742
973838293
1216113038
1047221747
736327832
1215425303
1047304275
1091438394
1225702384
453387356
526687785
738617539
1091438394
1103819800
1092136148
966077712
1215425303
1092136148
687247521
981794289
1110106267
681492034
1280...

result:

wrong answer 1st numbers differ - expected: '133792261', found: '893906810'

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 9844kb

input:

4997 4999 4996
2 4368 4799
2 2119 4764
2 4434 4464
1 2035 4706 4296
1 519 522 2387
2 3 2084
1 4748 4755 461
2 2812 4626
1 4801 4805 2427
1 611 615 2155
2 772 2397
2 1443 2197
2 392 792
1 3032 3036 2776
2 3148 4757
1 3661 3678 3968
1 3901 3921 2378
1 143 164 531
1 3337 3360 3189
2 679 2911
1 1436 145...

output:

7969790228
9845620194
4887485945
7867183052
5014914699
7014849584
3539883213
9412065625
9857983380
6957041585
7833543220
8407271551
9334029052
8358352790
6388435155
5428497419
7860886226
6049784302
5204011679
4259075787
2181598299
8803723794
3574478374
9796128195
2972127537
9378228552
3095505993
158...

result:

wrong answer 1st numbers differ - expected: '170506488', found: '7969790228'

Test #7:

score: 5
Accepted
time: 342ms
memory: 48172kb

input:

499998 499998 500000
2 45317 481911
2 205023 267850
2 229212 496395
2 311928 408362
2 60781 309919
2 5271 471569
2 428188 498422
2 92261 439291
2 169892 354633
2 154209 351949
2 39872 442239
2 17793 200874
2 111458 165313
2 35630 448969
2 144408 434923
2 150127 486605
2 87239 425125
2 221549 283735
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 500000 numbers

Test #8:

score: 5
Accepted
time: 304ms
memory: 46588kb

input:

499996 500000 499996
2 416226 432058
2 352324 435508
2 284349 418508
2 331919 481387
2 123642 260653
2 443789 449866
2 304455 480845
2 25402 269023
2 88509 334117
2 91159 399658
2 354630 412055
2 27378 126849
2 43994 304769
2 352338 413477
2 441505 499446
2 230203 287653
2 386 34219
2 77130 483544
2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499996 numbers

Test #9:

score: 5
Accepted
time: 303ms
memory: 47864kb

input:

499999 499997 499996
1 242721 499999 95404
2 46103 133768
2 374074 441419
1 24121 24525 460791
1 296358 334367 213389
1 333891 339996 192126
2 271641 289312
1 159292 235107 359363
2 281766 283959
2 68186 255669
2 112532 201134
2 281439 287449
2 265345 398433
1 495720 499897 85179
2 336233 383598
1 3...

output:

2468271622976502
4698221336203047
2464245485338876
645680549315240
4137175050453070
3950418188801308
3431179684492738
4522966461353266
3166686806745582
5749341684382686
5655992044074729
5040293282968353
5319677263051754
788536277093141
5728837186825024
5510473350313701
3529728904982101
4619416125356...

result:

ok 499996 numbers

Test #10:

score: 5
Accepted
time: 351ms
memory: 42608kb

input:

499996 499998 499996
2 127334 135648
2 250092 494065
2 202618 237080
1 365995 485247 159366
1 461761 461763 167619
1 161295 165395 156081
2 118953 278863
1 31995 32188 13920
2 211226 376698
2 125014 312511
1 248692 248694 369316
2 23909 438451
1 90793 222688 109394
1 405548 405549 283104
2 54420 263...

output:

6052992577626026
3382664487353801
1884084119561139
4903775722926407
3210035234431531
3584335605288938
884213945547262
3295062490109691
4664629263400943
2239831274910685
4245332811417453
3615086157849446
3713704632609047
2853449777151749
3326297007912742
1693113899010582
5193547170079661
610678361763...

result:

ok 499996 numbers

Test #11:

score: 5
Accepted
time: 305ms
memory: 46448kb

input:

499999 499996 500000
1 263967 499999 193060
1 473673 473677 256364
1 112817 112820 147747
2 47560 75007
1 19751 19754 272463
1 147343 147345 432368
1 385248 385251 111981
1 98114 98117 384182
1 186894 186898 304739
1 13283 13285 1641
1 127923 127925 168790
2 59949 123247
2 76677 91972
1 138037 13803...

output:

990441926198121
1131783204405760
1841594455443916
1429945764520838
1342322224927645
1189072840223364
1018063528311989
559620378260513
989097224237378
1518129837354668
1867723561760663
1760356304733675
1042878888480154
1649535653395098
1368639223606920
267228899642801
1263976363580744
747690120151501...

result:

ok 500000 numbers

Test #12:

score: 5
Accepted
time: 362ms
memory: 47212kb

input:

499999 499995 499997
1 163879 499999 440480
2 420164 470414
1 443882 499999 62525
1 313171 499999 294789
1 469407 469540 44668
2 25119 191405
2 172689 455667
2 110136 338451
2 218391 398188
1 486533 486654 93435
2 95706 256203
2 196989 304612
2 326480 401308
2 54460 198784
1 271793 271898 320340
2 9...

output:

9516852927305017
7740338485216257
1198276228367318
10740427176028746
7674707228336123
6385948644427168
8993322822222657
11525476199693268
8372851884764686
10841604116388888
4624556391191823
9183227648165112
12553205632815966
9069610675997904
11813755319797578
12039992183277874
9698983844179363
10370...

result:

ok 499997 numbers

Test #13:

score: 0
Wrong Answer
time: 151ms
memory: 27220kb

input:

200000 200000 200000
2 31803 80740
2 112818 127167
1 131322 154428 90611
2 11014 192282
2 41925 115417
2 5816 159028
2 111819 126655
2 37293 172866
2 27835 145099
2 124446 162824
2 104521 118016
2 40376 127391
1 195318 195319 149596
2 41040 179839
2 61847 94626
2 69878 181705
2 28968 179132
2 132543...

output:

74600085995823
147567615383136
154024060469100
305851463151114
67605298219022
141840622741953
294629792721820
248569243128021
248606152728039
231817208289154
57443677900942
270099210522695
147123191553518
243684711974609
50562738700449
172408838576192
67844488439068
167844882685179
263585140347984
1...

result:

wrong answer 1st numbers differ - expected: '11850130543160', found: '74600085995823'

Test #14:

score: 0
Wrong Answer
time: 119ms
memory: 26636kb

input:

199995 199998 199998
1 159195 199995 13044
2 86976 157151
1 64762 102114 152625
1 61813 63647 178420
1 82889 85481 125381
1 51586 54321 77506
2 45182 109756
1 181575 184132 133556
2 28331 132281
2 17325 40861
2 42257 191103
2 147228 198059
2 75171 155696
1 139100 140799 154126
1 188327 190311 76827
...

output:

275373132583440
623609165334304
489149823692502
274441509632900
282740177416286
421529735650002
372491318431367
196464536092640
652997349294837
586711256416423
314550773610233
605361560572441
259604181226141
213455243066966
317318021315761
632057269117277
640006666988826
410691929249873
499594980645...

result:

wrong answer 1st numbers differ - expected: '79495501365687', found: '275373132583440'

Test #15:

score: 0
Wrong Answer
time: 143ms
memory: 24352kb

input:

199999 199996 200000
1 179926 199999 32711
1 1042 1044 112146
2 26640 43359
1 178347 178351 169789
2 32064 164957
2 81951 117742
1 179853 179856 73377
2 66862 193241
2 10596 28181
2 49117 162750
1 13331 13333 43998
2 26996 197910
1 161366 161369 84391
2 127515 184183
1 66412 66416 97202
2 49708 5634...

output:

39796293955042
31985493950182
246298319939977
82285609554675
129658160125357
212879480845577
47328874682447
74810640209999
150624938634117
207514217201840
339902621340935
185969771522170
105395366321846
60360954073028
16949599033082
335933392249233
246344078967613
252222913926652
272803010565576
501...

result:

wrong answer 1st numbers differ - expected: '30619262894537', found: '39796293955042'

Test #16:

score: 0
Wrong Answer
time: 157ms
memory: 24268kb

input:

200000 200000 200000
1 59821 200000 173244
1 190307 190309 110936
1 112341 112342 4761
1 124738 124740 84834
1 3047 3049 102534
2 114052 180833
2 72832 109679
2 84797 91295
1 191583 191584 141834
1 185318 185320 87703
1 117000 117002 109533
1 80539 80540 105603
1 24207 24209 111543
1 83298 83299 140...

output:

137571126207079
182762683622389
122417208342283
43184482209335
185924056459731
167248042655009
149947020475393
173748577306948
155677255520760
142220239408076
113492655142536
181741632757907
178589743889135
110839034084605
115170614481244
166714627266366
36515222744423
95180541576031
174716761175683...

result:

wrong answer 1st numbers differ - expected: '33260996367776', found: '137571126207079'

Test #17:

score: 0
Wrong Answer
time: 382ms
memory: 46332kb

input:

500000 500000 500000
2 430331 460074
1 364723 500000 100669
1 250319 250342 82754
1 438542 441692 403146
1 463281 463283 433598
2 257762 468063
2 48944 155558
2 353640 481169
1 84674 84675 290827
2 146697 229831
2 468564 488452
2 5108 66751
1 23182 45112 201883
2 282890 447793
1 32871 33375 376198
1...

output:

2380185702443964
2783352583812215
3089790112415079
1413866045193762
2360911278236236
3691167411552463
3763571886367247
1099439162229164
2278479567703728
16033105876906
2101144005899161
771548196558000
3129470705896414
1160053869962303
1375525825337392
840803895827302
879722427783704
3720173706288768...

result:

wrong answer 1st numbers differ - expected: '1942220657726821', found: '2380185702443964'

Test #18:

score: 0
Wrong Answer
time: 338ms
memory: 47792kb

input:

500000 499995 499999
2 227886 411572
2 211683 333769
1 250096 500000 235662
1 426728 426927 304290
2 57626 245045
2 274989 390864
2 128937 178776
1 131741 131862 102941
1 98436 98438 22052
1 166478 166479 223278
1 450334 450336 468682
1 235946 235947 469845
1 472838 472839 386149
1 94197 94199 37254...

output:

4524658555143624
4760942730002498
3450325229103030
3485608086049920
3693014354406156
1796188776690093
2486141874656180
4633975877064212
3295711910419215
3757446711233875
752147886869684
4099327308379576
1661107886121333
2855390143470583
4166963257635453
4859865035858362
3884928845684053
375799030545...

result:

wrong answer 1st numbers differ - expected: '1934994488313802', found: '4524658555143624'

Test #19:

score: 0
Wrong Answer
time: 332ms
memory: 42780kb

input:

500000 500000 500000
1 483553 500000 33628
1 469113 469115 99122
2 331771 461807
2 132277 227909
1 409018 409020 67790
2 239961 327023
2 71363 250145
2 194504 394975
2 112739 357223
2 29586 226312
1 365927 365929 56596
2 37108 464107
2 260079 467849
1 132248 132250 77986
2 192853 237448
2 361959 386...

output:

3964159658258745
4173237855262578
1152553711811871
152873587085782
4253728246441389
4317937490094193
3611188376199648
2062408328484194
1586892107201883
992765963252416
1447077428060964
1011586600523726
4189538044605705
913633265027553
3683817414139593
3801883194690341
687358462985271
407558117078954...

result:

wrong answer 1st numbers differ - expected: '2430481205529290', found: '3964159658258745'

Test #20:

score: 0
Wrong Answer
time: 352ms
memory: 48200kb

input:

499999 499999 499996
2 212908 238055
1 460268 499999 317714
2 420753 465452
1 184130 194219 347230
1 24358 31202 484414
2 261874 280744
1 382916 389593 121902
2 998 230297
1 83691 94553 138191
2 357537 469176
1 478043 489289 9664
2 49390 163924
1 496313 499999 485644
2 307553 482205
1 148359 158827 ...

output:

6498516711627878
9125998524154022
9647885822559764
11444085698016787
7599047129334941
9725917946820783
8930506404562329
5113394288302619
2186530380475158
7730824083184477
9936809546343460
11320458939891653
2330074793565933
8829701674155589
10023017173266094
10673170684615531
11771375332972256
696957...

result:

wrong answer 1st numbers differ - expected: '168449195555655', found: '6498516711627878'