QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232149 | #6608. Descent of Dragons | grass8cow | WA | 1ms | 10032kb | C++14 | 1.5kb | 2023-10-29 22:30:03 | 2023-10-29 22:30:03 |
Judging History
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'