QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#232149#6608. Descent of Dragonsgrass8cowWA 1ms10032kbC++141.5kb2023-10-29 22:30:032023-10-29 22:30:03

Judging History

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

  • [2023-10-29 22:30:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:10032kb
  • [2023-10-29 22:30:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,q,a[500100],B,is[500100],L[810],R[810];
vector<int>g[810];
int mx[810];
#define pb push_back
int fa[500010],ab[501000],wh[501000];
int F(int x){
	if(x==fa[x])return x;
	return fa[x]=F(fa[x]);
}
void cg(int e){
	if(g[e].empty())return;
	for(int i=L[e];i<=R[e];i++){
		if(!ab[a[i]])ab[a[i]]=i,fa[i]=i,wh[i]=a[i];
		else fa[i]=ab[a[i]];
	}
	for(int x:g[e]){
		if(ab[x]&&ab[x+1])fa[ab[x]]=ab[x+1],ab[x]=0;
		else if(ab[x])ab[x+1]=ab[x],ab[x]=0,wh[ab[x+1]]=x+1;
	}
	for(int i=L[e];i<=R[e];i++)a[i]=wh[F(i)];
	for(int i=L[e];i<=R[e];i++)ab[wh[i]]=0;
}
int main(){
	scanf("%d%d",&n,&q);B=sqrt(n);
	for(int i=1;i<=n;i++)is[i]=(i-1)/B+1;
	for(int i=1;i<=is[n];i++){
		L[i]=(i-1)*B+1,R[i]=min(n,i*B);
	}
	for(int ii=1,ty,l,r,z;ii<=q;ii++){
		scanf("%d%d%d",&ty,&l,&r);
		int lp=is[l],rp=is[r];
		cg(lp);if(lp<rp)cg(rp);
		if(ty==1){
			scanf("%d",&z);
			if(lp!=rp){
				for(int i=l;i<=R[lp];i++)if(a[i]==z)a[i]=z+1,mx[lp]=max(mx[lp],z+1);
				for(int i=L[rp];i<=r;i++)if(a[i]==z)a[i]=z+1,mx[rp]=max(mx[rp],z+1);
			}
			else{for(int i=l;i<=r;i++)if(a[i]==z)a[i]=z+1,mx[lp]=max(mx[lp],z+1);}
			for(int i=lp+1;i<rp;i++){
				g[i].pb(z);
				if(mx[i]==z)mx[i]=z+1;
			}
		}
		else{
			int ans=0;
			if(lp!=rp){
				for(int i=l;i<=R[lp];i++)ans=max(ans,a[i]);
				for(int i=L[rp];i<=r;i++)ans=max(ans,a[i]);
			}
			else{for(int i=l;i<=r;i++)ans=max(ans,a[i]);}
			for(int i=lp+1;i<rp;i++)ans=max(ans,mx[i]);
			printf("%d\n",ans);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7932kb

input:

5 5
1 3 5 0
1 1 4 1
1 1 5 2
2 2 2
2 4 5

output:

0
3

result:

ok 2 number(s): "0 3"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 10032kb

input:

1000 1000
2 234 913
1 693 735 47
1 702 959 94
2 273 286
1 814 896 47
1 560 566 15
1 46 699 97
2 494 527
1 721 879 68
1 87 437 26
1 163 938 15
1 816 912 58
2 284 670
2 713 763
1 49 542 13
1 669 874 41
2 795 855
1 601 962 93
1 413 747 50
1 528 710 73
2 255 435
1 329 871 86
1 24 236 48
1 22 48 41
1 29 ...

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
1
0
0
1
0
1
0
0
0
0
0
2
3
0
2
0
0
0
0
2
0
2
2
2
2
2
3
3
3
2
2
0
0
2
0
0
0
3
3
3
0
0
0
3
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
4
3
4
4
10
10
3
3
16
3
3
5
3
3
5
4
5
4
26
4
30
6
5...

result:

wrong answer 39th numbers differ - expected: '2', found: '3'