QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#446347	#4214. Deja Vu	Pure_Furies	TL	277ms	159760kb	C++14	2.8kb	2024-06-17 08:40:19	2024-06-29 06:57:01

Judging History

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

[2024-06-29 06:57:01]
管理员手动重测本题所有提交记录

测评结果：TL
用时：277ms
内存：159760kb

查看

[2024-06-28 21:31:34]
hack成功，自动添加数据
(/hack/708)

[2024-06-17 08:40:21]
评测

测评结果：0
用时：269ms
内存：159748kb

查看

[2024-06-17 08:40:19]
提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int w[1048576][32],I,G[2];
int msk,pm[16][2];
void pu(int k){
	memset(w[k],0,64);
	for(int i=2;i<16;i+=2){
		pm[i][0]=((i&2)||w[k<<1][i>>1]!=w[k][pm[(i>>2)<<1][0]])+pm[(i>>2)<<1][0]<<1;
		pm[i][1]=((i&2)||w[k<<1|1][i>>1]!=w[k][pm[(i>>2)<<1][1]])+pm[(i>>2)<<1][1]<<1;
		if(w[k][pm[i][0]]<w[k<<1][i])
			w[k][pm[i][0]|1]=max(w[k][pm[i][0]],w[k<<1][i|1]),
			w[k][pm[i][0]]=w[k<<1][i];
		else
			w[k][pm[i][0]|1]=max(w[k][pm[i][0]|1],w[k<<1][i|(w[k][pm[i][0]]==w[k<<1][i])]);
		if(w[k][pm[i][1]]<w[k<<1|1][i])
			w[k][pm[i][1]|1]=max(w[k][pm[i][1]],w[k<<1|1][i|1]),
			w[k][pm[i][1]]=w[k<<1|1][i];
		else
			w[k][pm[i][1]|1]=max(w[k][pm[i][1]|1],w[k<<1|1][i|(w[k][pm[i][1]]==w[k<<1|1][i])]);
	}
}
int mp[32];
void PD(int k,int *F){
	for(int K=(k<<1);K<(k+1<<1);K++){
		F[K&1]=0;
		for(int i=2;i<32;i+=2){
			mp[i]=((i&2)||w[K][i>>1]!=w[k][mp[(i>>2)<<1]])+mp[(i>>2)<<1]<<1;
			w[K][i]=min(w[K][i],w[k][mp[i]]);
			if(msk&1<<mp[i])
				F[K&1]|=1<<i;
		}
	}
	for(int i=16;i<32;i+=2)
		w[k][i]=1e9;
}
void op(int _l,int _r,int l,int r,int k,int x,int v){
	if(l>_r||r<_l||l>r)return;
	int F[2],A,B=0;
	if(l<=_l&&_r<=r){
		while(v){
			A=0;
			for(int i=2;i<16;i+=2)
				if(1<<i&v)
				if(w[k][i]<x){
					if(i<8)
						A|=(1<<(i<<1)),
						A|=(4<<(i<<1));
					else
						w[k][i<<1]=min(w[k][i<<1],I),
						w[k][i+1<<1]=min(w[k][i+1<<1],I);
				}else if(w[k][i+1]<x){
					w[k][i]=min(w[k][i],x);
					if(i<8)
						A|=(4<<(i<<1));
					else
						w[k][i+1<<1]=min(w[k][i+1<<1],I);
				}else B|=1<<i;
			v=A;
		}
	}else B=v;
	if(!B)return;
	msk=B;
	PD(k,F);msk=0;
	op(_l,_l+_r>>1,l,r,k<<1,x,F[0]);
	op(_l+_r+1>>1,_r,l,r,k<<1|1,x,F[1]);
	pu(k);
}
void rmk(int l,int r,int p,int k){
	if(l==r){
		for(int i=2;i<32;i+=2)
			w[k][i]=1e9;
		return;
	}
	PD(k,G);
	if(p<=(l+r>>1)) 
		rmk(l,l+r>>1,p,k<<1);
	else
		rmk(l+r+1>>1,r,p,k<<1|1);
	pu(k);
}
int n,T,m,v;
vector<pair<int,int> >opt[500003];
vector<int>qr[500003];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>T;
	for(int i=0;i<1048576;i++)
		for(int j=2;j<32;j+=2)
			w[i][j]=1e9;
	for(int i=0;i<n;i++){
		cin>>v;
		opt[i].push_back({0,v});
	}
	while(T--){
		int tp,i;
		cin>>tp>>i;i--;
		if(tp==1){
			cin>>v;
			opt[i].push_back({m,v});
		}else
			qr[i].push_back(m++);
	}
	for(I=0;I<n;I++){
		for(auto j:qr[I])
			rmk(0,524287,j,1);
		opt[I].push_back({m,0});
		for(int j=0;j+1<opt[I].size();++j)
			if(opt[I][j].first!=opt[I][j+1].first)
				op(0,524287,opt[I][j].first,opt[I][j+1].first-1,1,opt[I][j].second,4); 
	}
	for(int i=1;i<524288;i++)PD(i,G);
	for(int i=0;i<m;i++)
		if(w[i+524288][16]<n)
			cout<<w[i+524288][16]+1<<'\n';
		else
			cout<<"-1\n";
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 45ms

memory: 158260kb

input:

11 10
1 2 3 4 5 10 9 8 7 6 8
2 1
1 3 2
2 1
1 1 2
2 1
2 5
2 6
1 9 6
1 10 7
2 5

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 38ms

memory: 158204kb

input:

6 7
2 3 6 10 2 3
2 3
2 1
2 5
2 4
1 4 7
1 2 3
1 4 4

output:

-1
4
-1
-1

result:

ok 4 number(s): "-1 4 -1 -1"

Test #3:

score: 0

Accepted

time: 35ms

memory: 158136kb

input:

output:

-1
-1
-1

result:

ok 3 number(s): "-1 -1 -1"

Test #4:

score: 0

Accepted

time: 45ms

memory: 158188kb

input:

10 8
3 3 7 10 4 10 5 10 4 6
1 7 1
1 2 6
1 3 3
2 1
2 3
2 2
2 10
1 6 8

output:

-1
-1
-1
-1

result:

ok 4 number(s): "-1 -1 -1 -1"

Test #5:

score: 0

Accepted

time: 37ms

memory: 158244kb

input:

3 1
2 7 6
1 1 6

output:

result:

ok 0 number(s): ""

Test #6:

score: 0

Accepted

time: 34ms

memory: 158256kb

input:

6 9
5 3 10 1 4 8
2 4
2 5
1 6 9
2 6
1 2 8
2 6
1 6 6
2 6
2 3

output:

-1
-1
-1
-1
-1
-1

result:

ok 6 numbers

Test #7:

score: 0

Accepted

time: 40ms

memory: 158128kb

input:

output:

-1
-1

result:

ok 2 number(s): "-1 -1"

Test #8:

score: 0

Accepted

time: 40ms

memory: 158188kb

input:

8 9
1 6 5 8 4 2 2 8
1 6 8
2 1
2 4
1 6 3
1 3 8
2 4
2 3
2 4
2 6

output:

-1
-1
-1
-1
-1
-1

result:

ok 6 numbers

Test #9:

score: 0

Accepted

time: 49ms

memory: 158204kb

input:

8 10
217400736 245088203 438403019 544276344 623130600 771196890 806732388 943246485
1 5 597885336
2 4
1 4 467449103
2 4
2 1
2 7
2 1
1 8 895177001
2 6
2 1

output:

result:

ok 7 numbers

Test #10:

score: 0

Accepted

time: 52ms

memory: 158248kb

input:

9 10
193163402 243977660 377454846 464717358 505938403 645114858 737147728 896624758 907949852
2 7
2 2
1 8 815720321
1 4 493251485
2 7
1 3 337311288
1 6 634446148
1 7 777046439
1 3 348388680
1 3 365967702

output:

-1
5
-1

result:

ok 3 number(s): "-1 5 -1"

Test #11:

score: 0

Accepted

time: 40ms

memory: 158132kb

input:

11 12
85526606 329382857 394199721 497022557 467462442 598693728 552286093 799983855 866068842 850488024 951465304
2 8
1 6 440234998
1 10 973849238
2 4
2 8
1 3 296857547
1 7 659027526
1 2 170353108
1 3 294186048
1 7 532972742
2 9
2 10

output:

-1
9
-1
-1
-1

result:

ok 5 number(s): "-1 9 -1 -1 -1"

Test #12:

score: 0

Accepted

time: 44ms

memory: 158184kb

input:

17 12
81700615 177358844 210484653 210027365 339128965 387608288 406322108 521926061 534447685 650723289 612710353 643285058 708879134 761413753 914021166 878531863 947497596
2 2
1 11 582959768
1 9 547592964
1 8 511979012
2 4
2 11
1 11 562446299
1 5 383781991
2 6
2 5
1 1 144692431
2 15

output:

result:

ok 6 numbers

Test #13:

score: 0

Accepted

time: 39ms

memory: 158132kb

input:

16 20
107686776 187399557 261923862 271763306 275071944 329173892 426516538 443145534 527414173 683878357 635498457 740630422 848403640 813320023 889976700 976183503
2 11
2 1
1 7 415631805
2 10
1 11 762634175
2 4
2 7
1 12 709031691
2 10
2 13
2 2
2 4
2 16
2 1
1 11 716122093
2 6
1 1 70063421
2 9
1 8 5...

output:

result:

ok 14 numbers

Test #14:

score: 0

Accepted

time: 44ms

memory: 158244kb

input:

13 12
156189537 143195484 180384697 326238301 488125041 482236236 560273273 549954003 573091577 723307221 729723772 947621215 930274243
1 9 737120303
1 4 280169823
1 6 373132039
2 3
2 3
2 4
1 5 433523095
1 6 435547215
1 11 800378380
1 7 579236843
1 8 564152858
2 5

output:

result:

ok 4 number(s): "7 7 9 9"

Test #15:

score: 0

Accepted

time: 40ms

memory: 158252kb

input:

18 19
59610219 122962133 162846878 243630045 227212798 312668404 382475181 485322503 552195231 522627834 637369897 716064716 761450540 793669806 852048828 825968217 932181701 969223872
2 13
2 10
1 13 758223974
1 3 116194810
2 4
2 12
1 13 773203784
1 17 964126579
2 4
1 2 123312890
2 9
2 15
1 1 756492...

output:

result:

ok 11 numbers

Test #16:

score: 0

Accepted

time: 42ms

memory: 158136kb

input:

195 124
14982138 14340371 21995736 15372479 29336424 34074870 40351882 36579502 54997653 57485403 62760845 63820611 72591491 72101224 82413793 86127668 94240185 87684082 97876299 104326166 105368645 121670981 112481616 121624907 124864528 139713173 138666696 148743068 157548284 148185712 166462219 1...

output:

result:

ok 65 numbers

Test #17:

score: 0

Accepted

time: 43ms

memory: 158232kb

input:

481 208
4427829 2791666 9240280 12378824 9086399 14302785 18360122 17551102 18033637 19893562 26729687 28132448 27081770 32159393 32421041 34524503 38394864 37843353 41979211 40997165 45769610 45833001 51006968 51957236 55063648 53788674 59676931 59564031 58646263 61740940 66753955 68929118 67757973...

output:

result:

ok 93 numbers

Test #18:

score: 0

Accepted

time: 43ms

memory: 158284kb

input:

383 492
3825364 8239320 9700611 8602345 14451115 20824368 23019406 25834506 27477784 23569339 27498227 30647271 31753323 37730561 42280048 41245122 43077145 51423216 54624407 56391663 53702148 55484564 64667404 64473778 66054081 67763248 72245663 77335769 76454411 76103218 79407064 85558573 86318518...

output:

result:

ok 248 numbers

Test #19:

score: 0

Accepted

time: 49ms

memory: 158152kb

input:

36 499
949563491 936519709 924916927 895053248 854787338 828947833 793617419 814775908 734615977 738150932 714741162 724958289 698239960 663519437 645079621 542385269 529754602 492361836 519469354 442234937 426538210 380542231 374271617 332246729 355264370 296203702 269581427 275177171 195147255 175...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 266 numbers

Test #20:

score: 0

Accepted

time: 47ms

memory: 158228kb

input:

399 235
998046309 996656147 993823957 991906931 992171052 987368672 986867819 983098593 975544961 973171106 973473472 967590126 969338289 965200807 964711940 964064315 962390073 959707924 952880810 947965073 947964928 947535641 943184735 938388913 939579771 934493926 935215622 934907551 931908207 92...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 116 numbers

Test #21:

score: 0

Accepted

time: 36ms

memory: 158200kb

input:

44 313
994520608 956056574 956365026 898208706 884750341 886864131 848188052 803692416 830508038 775479109 752797833 763616424 696894356 718139948 659504525 671719169 613198941 598382002 574971436 540054882 549948381 513261611 489523582 481704805 428512129 452322618 428175381 361212522 391709550 336...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 164 numbers

Test #22:

score: 0

Accepted

time: 31ms

memory: 158248kb

input:

13 116
972728992 896720334 814542532 705222488 706483145 557075980 462311520 431032677 468166449 337717590 345520949 240374290 171270777
1 8 562739167
1 2 875866720
1 4 678061929
1 1 932888117
1 2 985595759
1 1 955298692
2 5
2 10
1 9 441537451
2 10
2 11
1 8 394515711
2 7
2 1
1 12 138019313
2 8
2 7
2...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 57 numbers

Test #23:

score: 0

Accepted

time: 35ms

memory: 158212kb

input:

359 338
994957002 996646569 990863516 991951270 986147723 988787303 979186329 980575877 975227298 972081128 972990837 964114560 966593071 960631341 956225015 956528774 953685841 951210770 950416501 947796926 945981249 938758280 937087509 933720792 934188097 929348476 930245343 924778901 924793681 91...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 174 numbers

Test #24:

score: 0

Accepted

time: 48ms

memory: 158220kb

input:

187 169
999769149 989266191 988824107 983455532 974019954 967731435 959694878 956806534 953257636 942738337 951695957 941578379 934957776 923302949 921743757 911009430 918234043 910838899 901214606 894766671 896579331 892828789 881290925 877465634 874083122 860423087 854728022 848355094 841699245 84...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 76 numbers

Test #25:

score: 0

Accepted

time: 48ms

memory: 158220kb

input:

272 193
997200981 992008970 993378381 989158492 984958692 981937381 979940197 975646797 973873251 965248253 957107501 960249234 953356966 955659853 942509454 947118835 936098597 934504735 932426340 925581033 920260613 920541013 922894177 912492900 911965364 908245656 900095708 899515683 895535358 88...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 103 numbers

Test #26:

score: 0

Accepted

time: 63ms

memory: 158312kb

input:

1159 3614
999893947 999053143 997609072 998397141 996402659 996486516 995637260 994015810 990665888 991144444 992795725 989712287 989232481 986583622 985809855 985406547 984777406 986671401 982847135 981423296 984430802 981799093 979397727 977772362 980070766 978202670 976594405 978184468 977283563 ...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
97
-1
-1
-1
-1
-1
-1
-1
-1
-1
97
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
97
-1
-1
-1
461
97
-1
-1
-1
-1
-1
97
-1
-1
97
461
-1
-1
97
461
461
-1
461
-1
461
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
461...

result:

ok 1792 numbers

Test #27:

score: 0

Accepted

time: 64ms

memory: 158316kb

input:

2459 3903
999909568 999929064 999199975 998567069 997415590 997742359 997400924 997890441 997117377 996184112 996516877 994628646 995226210 993674519 994824410 994172139 993670882 992184322 993020381 991356970 991318462 991510599 991340754 989945608 990280031 990600554 989837298 989711709 988620530 ...

output:

result:

ok 1984 numbers

Test #28:

score: 0

Accepted

time: 52ms

memory: 158268kb

input:

1848 2401
999461663 997921641 998606943 997577190 997452317 997063811 995605563 995370050 996203617 994276759 994457491 993699255 993575713 993469696 993388165 990484437 989735697 990229558 989770352 990367208 988672812 989527749 988244607 987627617 987847582 986493320 986296198 984789641 985596561 ...

output:

result:

ok 1165 numbers

Test #29:

score: 0

Accepted

time: 64ms

memory: 158428kb

input:

4203 3677
688477303 783919825 412687922 891170834 476006623 740071321 551591641 537273931 750346053 79471767 10250007 579772593 873929217 702600917 894799681 150368200 601912739 196251807 293868917 154765630 469060346 49369625 430659437 129019354 565284093 469271238 552490408 543198084 23661658 6080...

output:

result:

ok 1864 numbers

Test #30:

score: 0

Accepted

time: 40ms

memory: 158296kb

input:

953 200
616015938 303866647 556279378 535884282 360748191 109602991 222487076 515908243 399883764 770073466 241250580 244095552 746150682 304666635 583573652 320190567 270514558 43841820 512817073 497465466 286430274 286192071 670289782 617935789 38313178 565746472 219277924 991414394 202073070 7978...

output:

result:

ok 96 numbers

Test #31:

score: 0

Accepted

time: 108ms

memory: 158892kb

input:

16135 8128
281824907 496304344 39682632 149281884 266361235 616205944 663542279 945880009 322288462 916355934 489826877 427934673 955724949 655769803 570996087 995591508 897142827 835572040 473220393 814471777 78282370 203733985 32912498 370931168 289077699 531050019 194705570 385724758 721784980 32...

output:

result:

ok 4058 numbers

Test #32:

score: 0

Accepted

time: 265ms

memory: 159760kb

input:

26387 27762
999988451 999910185 999913353 999837724 999775762 999791696 999739889 999644074 999770080 999582981 999641561 999495997 999444272 999579429 999385115 999497655 999321746 999393922 999316550 999248847 999213109 999248298 999055090 999137721 999000925 999102106 998957346 999015311 99900805...

output:

result:

ok 14072 numbers

Test #33:

score: 0

Accepted

time: 277ms

memory: 159748kb

input:

26211 27792
999999316 999901645 999905449 999955767 999876466 999718932 999780764 999675563 999692074 999577987 999520413 999503924 999576189 999575026 999415817 999411655 999282811 999321536 999342557 999289888 999163200 999165756 999160451 999178205 998970761 999077290 999000545 999033264 99893380...

output:

result:

ok 13896 numbers

Test #34:

score: -100

Time Limit Exceeded

input:

500000 500000
999999883 999993680 999998293 999996195 999992637 999987483 999983088 999989853 999987940 999981903 999977240 999980164 999975079 999974695 999974212 999972803 999967221 999965344 999966462 999956155 999958220 999957770 999957804 999950728 999953167 999947241 999942888 999943254 999940...