QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#339155#8014. 新本格魔法少女C1942huangjiaxu10 1600ms97196kbC++143.1kb2024-02-26 20:17:482024-02-26 20:17:49

Judging History

This is the latest submission verdict.

  • [2024-02-26 20:17:49]
  • Judged
  • Verdict: 10
  • Time: 1600ms
  • Memory: 97196kb
  • [2024-02-26 20:17: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];
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;
			}
			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));return 0;
	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: 0
Wrong Answer
time: 11ms
memory: 49616kb

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:


result:

wrong answer Answer contains longer sequence [length = 100], but output contains 0 elements

Test #2:

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

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:


result:

wrong answer Answer contains longer sequence [length = 100], but output contains 0 elements

Test #3:

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

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:


result:

wrong answer Answer contains longer sequence [length = 5000], but output contains 0 elements

Test #4:

score: 0
Wrong Answer
time: 8ms
memory: 51216kb

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:


result:

wrong answer Answer contains longer sequence [length = 5000], but output contains 0 elements

Test #5:

score: 0
Wrong Answer
time: 8ms
memory: 50316kb

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:


result:

wrong answer Answer contains longer sequence [length = 4997], but output contains 0 elements

Test #6:

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

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:


result:

wrong answer Answer contains longer sequence [length = 4996], but output contains 0 elements

Test #7:

score: 5
Accepted
time: 16ms
memory: 53320kb

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: 25ms
memory: 52340kb

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: 1385ms
memory: 89380kb

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:


result:

wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements

Test #10:

score: 0
Wrong Answer
time: 1198ms
memory: 81164kb

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:


result:

wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements

Test #11:

score: 0
Wrong Answer
time: 1600ms
memory: 97196kb

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:


result:

wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements

Test #12:

score: 0
Wrong Answer
time: 1215ms
memory: 83112kb

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:


result:

wrong answer Answer contains longer sequence [length = 499997], but output contains 0 elements

Test #13:

score: 0
Wrong Answer
time: 210ms
memory: 64964kb

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:


result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #14:

score: 0
Wrong Answer
time: 308ms
memory: 67748kb

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:


result:

wrong answer Answer contains longer sequence [length = 199998], but output contains 0 elements

Test #15:

score: 0
Wrong Answer
time: 313ms
memory: 69832kb

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:


result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #16:

score: 0
Wrong Answer
time: 405ms
memory: 73964kb

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:


result:

wrong answer Answer contains longer sequence [length = 200000], but output contains 0 elements

Test #17:

score: 0
Wrong Answer
time: 1412ms
memory: 88840kb

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:


result:

wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements

Test #18:

score: 0
Wrong Answer
time: 1473ms
memory: 89640kb

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:


result:

wrong answer Answer contains longer sequence [length = 499999], but output contains 0 elements

Test #19:

score: 0
Wrong Answer
time: 1306ms
memory: 81472kb

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:


result:

wrong answer Answer contains longer sequence [length = 500000], but output contains 0 elements

Test #20:

score: 0
Wrong Answer
time: 1315ms
memory: 85396kb

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:


result:

wrong answer Answer contains longer sequence [length = 499996], but output contains 0 elements