QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#339176#8014. 新本格魔法少女C1942huangjiaxu30 3330ms104860kbC++143.2kb2024-02-26 20:31:482024-02-26 20:31:49

Judging History

This is the latest submission verdict.

  • [2024-02-26 20:31:49]
  • Judged
  • Verdict: 30
  • Time: 3330ms
  • Memory: 104860kb
  • [2024-02-26 20:31:48]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,B=3000,T=N/B+5;
typedef unsigned long long ll;
typedef unsigned int uint;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<class rd>
void read(rd &x){
	char c=getchar();
	for(;c<48||c>57;c=getchar());
	for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
uint n,m,q,l[N],r[N],v[N],a[N],p[N],id[N],tg[T],va[N],rv[N];
int d[N];
vector<tuple<uint,uint,ll> >e[N];
vector<pair<uint,ll> >g[N];
ll ans[N];
namespace b1{
	ll s1[N],s2[1<<10];
	uint lim;
	void init(){lim=m>>10;}
	inline void add(uint x,ll v){
		s1[x]+=v,s2[x>>10]+=v;
	}
	inline ll sum(uint x){
		ll res=0;
		for(uint i=0,j=1024-(x&1023);i<j;++i)res+=s1[x+i];
		for(uint i=(x>>10)+1;i<=lim;++i)res+=s2[i];
		return res;
	}
};
namespace b2{
	ll s1[N],s2[1<<10];
	inline void add(uint x,ll v){
		for(uint i=0,j=x&1023;i<j;++i)s1[x-i]+=v;
		for(uint i=0,j=x>>10;i<j;++i)s2[i]+=v;
	}
	inline void init(){
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
	}
}
void work(uint ln,uint k,uint t){
	for(uint i=1,x;i<=ln;++i)if(d[i]){
		x=p[i];
		b2::add(x,1ll*v[x]*d[i]);
		g[t].emplace_back(x,-1ull*k*v[x]*d[i]);
		d[i]=0;
	}
}
void solve(uint L,uint R){
	b2::init();
	uint k=0,tg=0,ln=0;
	for(uint i=1;i<=m;++i){
		if(l[i]>R||r[i]<L)goto ct;
		if(l[i]<=L&&R<=r[i]){
			if(!v[i])++k;
			else{
				if(tg){tg=i;goto ct;}
				for(int j=L;j<=R;++j)--d[a[j]];
				work(ln,k,i);
				ln=0,tg=i;
			}
		}else{
			if(!v[i])goto ct;
			uint _l=max(l[i],L),_r=min(r[i],R);
			if(tg){
				for(uint j=L;j<=R;++j)a[j]=1+(_l<=j&&j<=_r);
				p[1]=tg,p[2]=i;
				d[2]=_r-_l+1,d[1]=R-L+1-d[2];
				tg=0,ln=2;
			}else{
				p[++ln]=i,d[ln]=_r-_l+1;
				for(uint j=_l;j<=_r;++j)--d[a[j]],a[j]=ln;
				uint ct=0;
				for(uint j=1;j<=ln;++j)if(d[j])rv[j]=++ct,d[ct]=d[j],p[ct]=p[j];
				ln=ct;
				for(uint j=L;j<=R;++j)a[j]=rv[a[j]];
			}
			work(ln,k,i);
		}
		ct:;
		for(auto &[x,y,z]:e[i])z+=(b2::s1[x]+b2::s2[x-1>>10])*k;
	}
}
void bf(uint l,uint r,uint t){
	if(l>r)return;
	uint x=v[t],p=(l-1)/B;
	if(!x){
		if(tg[p])b1::add(tg[p],1ll*v[tg[p]]*(r-l+1));
		else for(uint i=l;i<=r;++i)b1::add(a[i],va[i]);
	}else{
		if(tg[p]){
			uint w=v[tg[p]];
			for(uint i=p*B+1,j=p*B+B;i<=j;++i)a[i]=tg[p],va[i]=w;
			tg[p]=0;
		}
		for(uint i=l;i<=r;++i)a[i]=t,va[i]=x;
	}
}
int main(){
	bool fg=true;
	read(n),read(m),read(q);
	b1::init();
	for(uint i=1;i<=m;++i){
		read(v[i]),read(l[i]),read(r[i]);
		if(v[i]==1)read(v[i]),fg=false;
		else v[i]=0;
	}
	if(fg){
		while(q--)puts("0");
		return 0;
	}
	for(uint i=1,l,r;i<=q;++i){
		read(l),read(r);
		e[r].emplace_back(l,i,0);
	}
	for(uint i=1;i<=n;i+=B)solve(i,min(i+B-1,n+1));
	for(uint i=1;i<=m;++i){
		uint lx=(l[i]+B-2)/B,rx=r[i]/B;
		if(lx>rx)bf(l[i],r[i],i);
		else{
			bf(l[i],lx*B,i),bf(rx*B+1,r[i],i);
			if(!v[i]){
				for(uint j=lx,x;j<rx;++j)if(x=tg[j])b1::add(x,v[x]*B);
			}else for(uint j=lx;j<rx;++j)tg[j]=i;
		}
		for(auto [x,y]:g[i])b1::add(x,y);
		for(auto &[x,y,z]:e[i])z+=b1::sum(x);
	}
	for(uint i=1;i<=m;++i)for(auto [x,y,z]:e[i])ans[y]+=z;
	for(uint i=1;i<=q;++i)printf("%lld\n",ans[i]);
	return 0;
}

详细

Test #1:

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

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: 3ms
memory: 56196kb

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: 10ms
memory: 57844kb

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:

234959455
32410138
47895605
1345462704
724730383
10261117
1238800857
2286160407
1372100175
1250348
369224776
153933829
520831805
1543145095
808001543
58489721
2696569
890882157
1961345701
12546381
22417560
464332609
5635795
179191833
86304800
76831918
735624550
39774953
7590133
1768988228
1098297916...

result:

wrong answer 7th numbers differ - expected: '1239181989', found: '1238800857'

Test #4:

score: 5
Accepted
time: 13ms
memory: 57940kb

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:

114655447
19433053
35915790
65614418
2476899
665630
20272239
61553396
72380629
114749301
65069600
881298
103684015
34129779
11855040
3208516
228433692
31692347
23672327
59493928
58289510
64897362
18474211
13657972
14996772
50859224
71046
84176051
533206
0
3412089
46601293
5753887
33429474
30861172
8...

result:

ok 5000 numbers

Test #5:

score: 5
Accepted
time: 14ms
memory: 56444kb

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:

133792261
139082018
293669691
3861707
34233830
279117403
1018970742
35243052
56047746
41576886
19209005
38995139
76194093
193774179
104584925
59187495
6752467
84435341
101847867
23142906
124266639
150193133
107905427
11004395
5034444
214897499
26673236
75854241
300218884
196777973
175768847
13761372...

result:

ok 4997 numbers

Test #6:

score: 0
Wrong Answer
time: 14ms
memory: 55644kb

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:

170506488
2306515380
938153261
2134416357
54235687
168306782
18267562
344703118
739174828
591025501
26125268
108119368
1290819177
506928908
1426082028
788984783
10847284
748464260
203208925
81559279
101223591
2226983822
6753446
18824
738638573
1027314200
91817035
361330271
1473051124
118945920
69916...

result:

wrong answer 3rd numbers differ - expected: '938807942', found: '938153261'

Test #7:

score: 5
Accepted
time: 21ms
memory: 52812kb

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: 21ms
memory: 52244kb

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: 2824ms
memory: 97700kb

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:

2444542374405716
4598485289874785
2440617465019533
645864578659519
4059320809126962
3879284502594156
3378704105610120
4430465068307568
3123069259057787
5594707371548279
5507127460479641
4924964686567460
5190189248905013
788619188909160
5575498890053405
5370214116464896
3473797991499782
4522990533621...

result:

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

Test #10:

score: 0
Wrong Answer
time: 3206ms
memory: 91088kb

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:

5935483482531886
3340985027594464
1870484653085579
4824239966242311
3172025576282301
3538285240473087
881028940105082
3255272497002958
4592129245119541
2220816968486731
4183961828451788
3568357810305303
3664774142215253
2823021467576335
3285817147106913
1682102637288770
5105190180721972
598728956527...

result:

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

Test #11:

score: 0
Wrong Answer
time: 2437ms
memory: 104860kb

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:

927650492609226
1052919994576055
1678991904038110
1314627509832559
1237755515676100
1103335462930896
952224259034174
537446936740771
926457816327373
1392219103079730
1702399387056483
1606586793510166
974254495534122
1508137275205450
1260876145147191
261141874137419
1169067967169447
709547941839033
3...

result:

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

Test #12:

score: 0
Wrong Answer
time: 3330ms
memory: 92152kb

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:

11087811809339807
9043138793705606
1284294714034388
12481528640231712
8966849724234864
7466267244106261
10488022429800808
13369972853749805
9773638129606241
12596253438114113
5389790363872104
10706227278381731
14533749267052077
10575639791266237
13696756971875088
13953123204400562
11296131200773570
...

result:

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

Test #13:

score: 0
Wrong Answer
time: 1103ms
memory: 72156kb

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:

10926823060009
22609952686400
8506078485870
57368832741544
1331184627999
58275677124475
10670076548955
32532238269509
2895380924308
68922962632728
4935530194655
23430814663670
66979596881044
33794558025891
13091715589614
46512985780210
9100859552812
20256581449034
9096267816750
58312647261035
165726...

result:

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

Test #14:

score: 0
Wrong Answer
time: 905ms
memory: 75136kb

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:

61170648006183
116174204230566
168746545338291
178320329553741
116842298803877
137520747898942
105766984751209
116983956315211
42965330319744
109926224413667
1855887851413
273101487828572
90073843403
499096336106
31235034975939
139669219677392
220062111006244
145301938691964
11814147094557
147918938...

result:

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

Test #15:

score: 0
Wrong Answer
time: 842ms
memory: 77076kb

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:

28528906986553
14738675333821
1723050231525
21402712979576
102162396212071
49816503161026
19644948341916
57923788917033
49863846839040
66769517672255
205191692551435
463738098610
6621227129228
27348179599451
13572807848716
267048613047487
190440466721569
236640558123658
40775808822
751041334425
9837...

result:

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

Test #16:

score: 0
Wrong Answer
time: 654ms
memory: 77288kb

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:

27389737949307
33182207947988
6817915052848
3282374900622
19296523162724
31689772259734
3071805078241
43947127437039
8975072880174
17627443343705
17878444135142
21582739533002
8140743727540
5360016881134
20197449762559
36305275605710
3076799414463
3736193426101
45223568993953
29056111446760
37107905...

result:

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

Test #17:

score: 0
Wrong Answer
time: 2730ms
memory: 96504kb

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:

1891687401902049
1692717748807
855956018988029
580759656300010
132689259864026
28556619562382
144806166889588
690101339240730
49728507124835
208024914642
1636949021574820
32971623770216
867361094090680
195179615989758
457853024933576
457203113594
1591197107
804973865795524
67104956000960
26799596517...

result:

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

Test #18:

score: 0
Wrong Answer
time: 2695ms
memory: 97940kb

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:

1473423578441721
652140143430696
274649745657713
180468281686281
100271596023740
379320375501146
527183756576945
658167171789986
1427774862860
1625373793996425
28290005583592
23066317934909
501025615395398
816396503259842
442729239857949
831191062058427
2316181644395900
561195800113866
2542351381681...

result:

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

Test #19:

score: 0
Wrong Answer
time: 3177ms
memory: 92844kb

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:

1849137550747747
1547919024825070
820108838495537
76274287893876
1576344448830288
42765637049606
568102828863724
62185431380654
582944601424947
238112235625723
1329002536035948
800156707268010
309425130678486
861234216001905
54550531755949
387835689593015
522538809449027
30847533714772
9387995805893...

result:

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

Test #20:

score: 0
Wrong Answer
time: 3185ms
memory: 94320kb

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:

168092752194087
1776318661027440
1823968570947925
2821167418452881
1215902274525391
351035214452073
814742611785910
59738156176186
123265900008205
345763949067642
1093945652968798
1462339445033259
92680676167321
1793796719607799
667369638257260
2479021884871939
1856285504507093
828526269073295
65415...

result:

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