QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#114817 | #6608. Descent of Dragons | Eric_cai | WA | 1ms | 13852kb | C++14 | 1.8kb | 2023-06-23 17:20:30 | 2023-06-23 17:20:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,q,cnt;
int ls[maxn*30],rs[maxn*30],rt[maxn],p[maxn*4],w[maxn*30],fa[maxn*30];
int build(int id,int l,int r)
{
int x=++cnt;
p[id]=x;
if(l==r) return x;
int mid=(l+r)>>1;
ls[x]=build(id<<1,l,mid);
rs[x]=build(id<<1|1,mid+1,r);
fa[ls[x]]=fa[rs[x]]=x;
return x;
}
int merge(int id1,int id2,int l,int r)
{
if(id1==0 || id2==0) return id1+id2;
if(l==r) return id1;
int mid=(l+r)>>1;
ls[id1]=merge(ls[id1],ls[id2],l,mid);
rs[id1]=merge(rs[id1],rs[id2],mid+1,r);
fa[ls[id1]]=fa[rs[id1]]=id1;
return id1;
}
int update(int id,int &id1,int &id2,int l,int r,int x,int y)
{
if(id1==0) return 0;
if(id2==0) id2=++cnt;
if(l>=x && r<=y)
{
id2=merge(id2,id1,l,r);
if(p[id]==id1) p[id]=id2;
id1=0;
return 1;
}
int mid=(l+r)>>1,ret=0;
if(x<=mid) ret+=update(id<<1,ls[id1],ls[id2],l,mid,x,y);
if(y>mid) ret+=update(id<<1|1,rs[id1],rs[id2],mid+1,r,x,y);
fa[ls[id1]]=fa[rs[id1]]=id1,fa[ls[id2]]=fa[rs[id2]]=id2;
if(l!=r && ls[id1]+rs[id1]==0) id1=0;
if(l!=r && ls[id2]+rs[id2]==0) id2=0;
if(ret>0) if(p[id]==id1) p[id]=id2;
return ret;
}
int query(int id,int l,int r,int x,int y)
{
if(l>=x && r<=y)
{
id=p[id];
while(fa[id]!=0) id=fa[id];
return w[id];
}
int mid=(l+r)>>1,ret=0;
if(x<=mid) ret=max(ret,query(id<<1,l,mid,x,y));
if(y>mid) ret=max(ret,query(id<<1|1,mid+1,r,x,y));
return ret;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int k,l,r,x;
cin>>n>>q;
rt[0]=build(1,1,n);
for(int i=1;i<=q;i++)
{
cin>>k>>l>>r;
if(k==1)
{
cin>>x;
if(x>q) continue;
w[rt[x]]=w[rt[x+1]]=0;
update(1,rt[x],rt[x+1],1,n,l,r);
w[rt[x]]=x,w[rt[x+1]]=x+1;
}
if(k==2) cout<<query(1,1,n,l,r)<<'\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 13852kb
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: 1ms
memory: 11832kb
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 2 0 2 0 0 0 0 2 0 2 2 2 2 2 2 2 2 2 2 0 0 2 0 0 0 3 3 3 0 0 0 1 1 1 3 2 2 2 2 3 1 3 2 2 3 3 2 2 1 3 2 3 3 3 3 3 3 3 2 2 3 3 2 3 2 1 3 3 2 1 3 3 3 1 1 2 2 3 2 1 1 3 3 2 2 2 3 2 3 2 3 2 2 3 3 2 2 1 2 3 2 3 4 4 3 4 2 4 2 4 4 4 ...
result:
wrong answer 143rd numbers differ - expected: '4', found: '3'