QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114817#6608. Descent of DragonsEric_caiWA 1ms13852kbC++141.8kb2023-06-23 17:20:302023-06-23 17:20:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-23 17:20:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:13852kb
  • [2023-06-23 17:20:30]
  • 提交

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'