QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308776#8014. 新本格魔法少女crazy_sea20 5642ms58592kbC++142.9kb2024-01-20 12:39:122024-01-20 12:39:13

Judging History

This is the latest submission verdict.

  • [2024-01-20 12:39:13]
  • Judged
  • Verdict: 20
  • Time: 5642ms
  • Memory: 58592kb
  • [2024-01-20 12:39:12]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10,B=600,K=N/B+1;
int n,m,Q,mx;
vector<pair<int,int>> v[N];
namespace b1//O(1) Modify
{
	ll t1[N],t2[N];
	void add(int x,ll a)
	{
		t1[x]+=a,t2[(x-1)/B]+=a;
	}
	ll qry(int x)
	{
		int k1=(x-1)/B,k2=(x-1)%B;
		ll s=0;
		for(int i=0;i<B-k2;i++) s+=t1[x+i];
		for(int i=k1+1;i<=mx;i++) s+=t2[i];
		return s;
	}
}
namespace b2//O(1) Query
{
	ll t1[2][N],t2[2][K+10];
	void add(int x,ll a,ll b)
	{
		int k1=x%B,k2=x/B;
		for(int i=0;i<k1;i++) t1[0][x-i]+=a,t1[1][x-i]+=b;
		for(int i=0;i<k2;i++) t2[0][i]+=a,t2[1][i]+=b;
	}
	void init()
	{
		for(int i=1;i<=m;i++) t1[0][i]=t1[1][i]=0;
		for(int i=0;i<K;i++) t2[0][i]=t2[1][i]=0;
	}
	ll qry(int x,int k)
	{
		int w=(x-1)/B;
		return t1[1][x]+t2[1][w]+(t1[0][x]+t2[0][w])*k;
	}
}
int p[N],id[N],d[N],l[N],r[N],a[N],tag[K+10];
ll ans[N],op[N];
void work(int len,int k)
{
	for(int i=1,x;i<=len;i++)
		if(d[i])
		{
			x=p[i];
			b2::add(x,1ll*op[x]*d[i],-1ll*k*op[x]*d[i]);
			d[i]=0;
		}
}
void solve(int L,int R)
{
	int num=0,tag=0,len=0;
	b2::init();
	for(int i=L;i<=R;i++) a[i]=0;
	for(int i=1;i<=m;i++)
	{
		if(l[i]>R||r[i]<L) continue;
		if(l[i]<=L&&R<=r[i])
		{
			if(op[i]==-1) num++;
			else
			{
				for(int i=L;i<=R;i++) d[a[i]]--;
				work(len,num);
				len=0,tag=i;
			}
		}
		else
		{
			if(op[i]==-1) continue;
			int x=max(l[i],L),y=min(r[i],R);
			if(tag)
			{
				for(int j=L;j<=R;j++)
					a[j]=1+(x<=j&&j<=y);
				len=2;
				p[1]=tag,p[2]=i;
				d[2]=y-x+1;
				d[1]=R-L+1-d[2];
			}
			else
			{
				p[++len]=i;
				for(int j=x;j<=y;j++)
					d[a[j]]--,d[a[j]=len]++;
			}
			work(len,num);
		}
		for(auto k:v[i]) ans[k.second]+=b2::qry(k.first,num);
	}
}
void brute(int l,int r,int k)
{
	if(l>r) return;
	int x=op[k],w=(l-1)/B;
	if(x==-1)
	{
		if(tag[k]) b1::add(tag[k],1ll*(r-l+1)*op[tag[k]]);
		else for(int i=l;i<=r;i++) b1::add(a[i],op[a[i]]);
	}
	else
	{
		if(tag[w])
			for(int i=(w-1)*B+1;i<=w*B;i++) a[i]=tag[w];
		for(int i=l;i<=r;i++) a[i]=k;
		tag[w]=0;
	}
}
int main()
{
//	freopen("mfsn.in","r",stdin);
//	freopen("mfsn.out","w",stdout);
	scanf("%d%d%d",&n,&m,&Q);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%d%d",&op[i],&l[i],&r[i]);
		if(op[i]==2) op[i]=-1;
		else scanf("%lld",&op[i]);
	}
	for(int i=1,l,r;i<=Q;i++)
	{
		scanf("%d%d",&l,&r);
		v[r].push_back({l,i});
	}
	for(int i=1;i<=n;i++) a[i]=0;
	for(int i=1;i<=m;i++)
	{
		int k1=(l[i]+B-2)/B,k2=r[i]/B;
		if(k1>k2) brute(l[i],r[i],i);
		else
		{
			brute(l[i],k1*B,i);
			brute(k2*B+1,r[i],i);
			if(op[i]==-1)
			{
				for(int j=k1,x;j<k2;j++)
					if((x=tag[j])) b1::add(x,op[x]*B);
			}
			else for(int j=k1;j<k2;j++) tag[j]=i;
		}
		for(auto k:v[i]) ans[k.second]=b1::qry(k.first);
	}
	for(int i=1;i<=n;i+=B)
		solve(i,min(i+B-1,n));
	for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 0ms
memory: 36724kb

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:

8086
19253
2809
6928
7105
24622
3358
0
1856
1260
78
172
17231
0
6163
2029
24290
1545
14375
3050
17203
23928
3560
6312
8103
11940
6267
17698
0
10720
19937
2310
2331
18774
923
125
10066
24991
788
27169
449
3028
0
25814
30943
31472
12850
14375
3364
613
4931
48343
13159
8086
14081
9783
1149
258
4690
181...

result:

ok 100 numbers

Test #2:

score: 5
Accepted
time: 0ms
memory: 35732kb

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:

0
700
5513
4848
0
0
5513
0
0
2751
10719
0
5885
0
0
172
1201
0
3067
0
0
1779
3835
0
172
2094
0
5946
0
0
7884
0
1651
0
6189
0
407
1081
0
3835
0
0
2593
5577
404
2751
407
13799
3369
0
3864
0
4702
5513
1779
7884
3974
0
700
1779
0
713
5941
6166
5230
0
0
478
0
2593
3067
1321
4123
172
0
0
6749
3036
1929
0
6...

result:

ok 100 numbers

Test #3:

score: 0
Wrong Answer
time: 7ms
memory: 36396kb

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:

74447625
15185070
10569030
245150359
145426263
4653108
308901773
252769359
122424323
660444
105682530
70991136
146506753
320852722
121254413
10482913
592507
402442871
103142559
6700833
10410053
75424165
899354
28111990
65135693
29327285
85244639
14378561
2695624
222556815
165325249
113438273
1144163...

result:

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

Test #4:

score: 0
Wrong Answer
time: 11ms
memory: 36512kb

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:

24417413
5570989
8213755
4184790
1717380
236734
6148743
6380182
15140213
23114960
2897044
199918
1769865
4736839
3556566
673124
38195696
992637
9709287
9010211
17297250
14024903
4201394
662459
4004969
77401
17464
65799251
1235304
0
490673
8338777
712751
2968643
6321540
11570973
1235304
1657916
0
104...

result:

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

Test #5:

score: 0
Wrong Answer
time: 5ms
memory: 35160kb

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:

32675397
23750247
58941264
1040699
10322165
14126502
34797325012
14181011
17068401
14044074
6651430
9985577
23194463
47680738
22573623
19574720
2294935
6721332
27557985
8392102
36630799
34500528
17083841
4420419
837403
7520189
10437674
8028129
51668786
31188259
15298346
47406556
58786506
120324774
7...

result:

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

Test #6:

score: 0
Wrong Answer
time: 3ms
memory: 35352kb

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:

87973207
42049789
139208006
133637332
16979433
39512654
11431717
101891410
101344750
106380410
7397571
20465334
266024706
75420502
393462017
10345696
14765421
77254160
46796312
20421794
31364111
503347388
3791875
2064
291326116
180081450
82873269
243545306
224403095
106326888
15232684
9707478
266384...

result:

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

Test #7:

score: 5
Accepted
time: 5642ms
memory: 54516kb

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: 5629ms
memory: 52468kb

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: 0
Wrong Answer
time: 3658ms
memory: 56484kb

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:

152377928479281
361125957292677
18706742755936
13292825998073
1077872542118001
376207132673791396
95960664358345306
21464427020532
241572756516067
167844916729350834
1651085382184400
230298861559713252
23198730221059
13719512208205
24274049011815
3113713236184244
293757573752958
19393682419595
26099...

result:

wrong answer 1st numbers differ - expected: '2468271622976502', found: '152377928479281'

Test #10:

score: 0
Wrong Answer
time: 4225ms
memory: 56560kb

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:

911669440146948
2640421790583102
174143550933937
698922808819414
24816004188023
21586952665705194
15442892352792673
22839805742912
114238333381013644
570185979478675
36894278946313971
25585618794401
158710512469739
46384810628472395
56171416606062
158792485190270
61717897484898029
334991330015097835...

result:

wrong answer 1st numbers differ - expected: '6052992577626026', found: '911669440146948'

Test #11:

score: 0
Wrong Answer
time: 3044ms
memory: 56480kb

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:

4152540451484
59383481725852
93226994557453
3641159270479
655493172636951
596181608644164
38291019057863
4804280232109
3900990429191
98414941655382
5622715128513
1143869363398050
1931276720339613
949971822451209
43647819016101
67781235937292
31999653633395
3173945576593
2808256403940
18654864181577
...

result:

wrong answer 1st numbers differ - expected: '990441926198121', found: '4152540451484'

Test #12:

score: 0
Wrong Answer
time: 4452ms
memory: 56620kb

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:

428960705821332
277130258881151277
95855802443738
93749237133021319
473204339849736293
176631283674079770
64713731947491
1014646831362709530
61229390224379278
884866370771025477
59868113353054
550146327108217611
556078614122105880
302514083561315
8427736132127824
1795596707783724
2261963942046685
88...

result:

wrong answer 1st numbers differ - expected: '9516852927305017', found: '428960705821332'

Test #13:

score: 0
Wrong Answer
time: 848ms
memory: 48580kb

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:

2949793315
21561022039904
101246382686
27686533667981
317909027230
285588696032
8424341818810
155884234376
2804842958722
14507907251249
4814024244447
17105544345392
164156255563
30143421223122
43313301145
36760820042338
537254894045
430808324376
3361019814167
9136264819383
9132735532595
496768964742...

result:

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

Test #14:

score: 0
Wrong Answer
time: 633ms
memory: 48568kb

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:

2295465850171
41957647836551
3515052761113
5504283873411810
261899173457473
1845269821830
5064354122554
4963642068567146
104938714566
184724577042626
857846541937
3668446967611
9681649459
28941282472
1609676840916
2281938466787
165747797621226
297522417632819
6370755819051
1790955617923
744474089724...

result:

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

Test #15:

score: 0
Wrong Answer
time: 667ms
memory: 50624kb

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:

114716909413
4725257707355
10465288632
125468894514
20796511533232
28257550252679
12997425911
66933605816
173444445639
180306213597
97598919989573
230969418081
38534329738
107662878507
13240926557126
110256140013337
3293199713
1156375559755
79573116
512331298826
29454965
394841616943
28041290096097
...

result:

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

Test #16:

score: 0
Wrong Answer
time: 551ms
memory: 48452kb

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:

31197590327009
154315977863
31827677864
21165973026
45346982353
147213004284
4452076036
24361932714087
49973361610
8576081459
16714795068
83546471725
46366097943
30630603065
77247219342
263763589709
4659155391
11171431524
390058575414
73780655636
179687924308
123709524715
3667601981
60837444308
3982...

result:

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

Test #17:

score: 0
Wrong Answer
time: 3902ms
memory: 56520kb

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:

3713323692325
929213496476
1917595913448
590917033846
85132243748164
35851979215981
129761275900572
311817317461198
76151269425
43502367144
1127354584916597
29220577982592
2086609400091
94281624652563
923927179915
29965121118
7559310
1774676741478
176681194519
1934373566175569
152543796240348
744914...

result:

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

Test #18:

score: 0
Wrong Answer
time: 3763ms
memory: 56476kb

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:

5071325411453
305791616321311
777090129958
713343564548
75356114454
700796771066
743704292853
371436836024420
1657143553370
1678296228064
49363847418
19616827461
789757065608
1202937391817
1287657480923
378143776051
334179895387
462817786473
580785435135
427971368058362
294978626112
1477875695947
25...

result:

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

Test #19:

score: 0
Wrong Answer
time: 4505ms
memory: 56568kb

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:

2174940109509891
4370330711392
590523410744935
5834064756993
1032861098540547
8557621736376
799386596623
80384067214722
402967724286688
150462659443
700087860097362
304989924532
10605909079825
215952814358
168771118184
1596744877025
170880023783789
19787344627
234793701112
177185790084
2413886805261...

result:

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

Test #20:

score: 0
Wrong Answer
time: 4774ms
memory: 58592kb

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:

242716362963
4795607873212
2171297257821612
1943656928885
1190371913805399
87973263237515
296299637662458
2636720946153
22813543466181
53929917451923
2485569510496
3641433486161
31232801796077
2187546208663
1252025521475
1876816873643892
289478330347
980503283571
1380413445043
59255883836509
1664160...

result:

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