QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425463#8179. 2D Parenthesesjinqihao2023RE 7ms41492kbC++144.4kb2024-05-30 11:22:252024-05-30 11:22:25

Judging History

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

  • [2024-05-30 11:22:25]
  • 评测
  • 测评结果:RE
  • 用时:7ms
  • 内存:41492kb
  • [2024-05-30 11:22:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,inf=2e9;
typedef unsigned long long ull;
int n,ax[N],ay[N],bx[N],by[N],cx[N],cy[N],a[N],pos[N];
mt19937_64 rd(19491001);
struct Seg_tree
{
	struct STree{int l,r,minn;}t[N*4];
	void pushup(int p){t[p].minn=min(t[p*2].minn,t[p*2+1].minn);}
	void build(int p,int l,int r)
	{
		t[p].l=l,t[p].r=r,t[p].minn=inf;if(l==r)return t[p].minn=a[l],void();
		int mid=l+r>>1;build(p*2,l,mid),build(p*2+1,mid+1,r),pushup(p);
	}
	void change(int p,int x,int v)
	{
		if(t[p].l==t[p].r)return t[p].minn=v,void();int mid=t[p].l+t[p].r>>1;
		if(x<=mid)change(p*2,x,v);else change(p*2+1,x,v);pushup(p);
	}
	int ask(int p,int l,int r)
	{
		if(l<=t[p].l && t[p].r<=r)return t[p].minn;
		int mid=t[p].l+t[p].r>>1,res=inf;
		if(l<=mid)res=min(res,ask(p*2,l,r));if(mid<r)res=min(res,ask(p*2+1,l,r));
		return res;
	}
}t1;
struct Seg_tree1
{
	struct STree{int l,r;ull tag,val;bool col;}t[N*4];
	void update(int p,ull v){t[p].tag^=v,t[p].val^=v;}
	void pushdown(int p){if(t[p].tag)update(p*2,t[p].tag),update(p*2+1,t[p].tag),t[p].tag=0;}
	void pushup(int p)
	{
		t[p].val=t[p*2].val;
		if(t[p*2].col && t[p*2+1].col && t[p*2].val==t[p*2+1].val)t[p].col=1;else t[p].col=0;
	}
	void build(int p,int l,int r)
	{
		t[p].l=l,t[p].r=r,t[p].col=1;if(l==r)return ;int mid=l+r>>1;
		build(p*2,l,mid),build(p*2+1,mid+1,r);
	}
	void change(int p,int l,int r,ull v)
	{
		if(l<=t[p].l && t[p].r<=r)return update(p,v);pushdown(p);
		int mid=t[p].l+t[p].r>>1;if(l<=mid)change(p*2,l,r,v);if(mid<r)change(p*2+1,l,r,v);
		pushup(p);
	}
	pair<ull,bool>ask(int p,int l,int r)
	{
		if(l<=t[p].l && t[p].r<=r)return {t[p].val,t[p].col};pushdown(p);
		int mid=t[p].l+t[p].r>>1;
		if(l>mid)return ask(p*2+1,l,r);if(mid>=r)return ask(p*2,l,r);
		pair<ull,bool>resl=ask(p*2,l,r),resr=ask(p*2+1,l,r);
		return {resl.first,(resl.second&resr.second&(resl.first==resr.first))};
	}
}t2;
bool cmp(int a,int b){if(by[a]!=by[b])return by[a]<by[b];return bx[a]<bx[b];}
int mat[N];
set<pair<int,int> >ss[N];
struct abc{int l,r;ull v;};
vector<abc>in[N],out[N];
ull vv[N];
bool cmp1(abc a,abc b){if(a.l!=b.l)return a.l<b.l;return a.r>b.r;}
bool cmp2(abc a,abc b){if(a.l!=b.l)return a.l>b.l;return a.r<b.r;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)vv[i]=rd();
	for(int i=1;i<=n;i++)scanf("%d %d",&ax[i],&ay[i]),cx[0]++,cx[cx[0]]=ax[i],cy[0]++,cy[cy[0]]=ay[i];
	for(int i=1;i<=n;i++)scanf("%d %d",&bx[i],&by[i]),cx[0]++,cx[cx[0]]=bx[i],cy[0]++,cy[cy[0]]=by[i];
	sort(cx+1,cx+cx[0]+1),cx[0]=unique(cx+1,cx+cx[0]+1)-cx-1;
	sort(cy+1,cy+cy[0]+1),cy[0]=unique(cy+1,cy+cy[0]+1)-cy-1;
	for(int i=1;i<=n;i++)ax[i]=lower_bound(cx+1,cx+cx[0]+1,ax[i])-cx,ay[i]=lower_bound(cy+1,cy+cy[0]+1,ay[i])-cy,bx[i]=lower_bound(cx+1,cx+cx[0]+1,bx[i])-cx,by[i]=lower_bound(cy+1,cy+cy[0]+1,by[i])-cy;
	for(int i=1;i<=n;i++)pos[i]=i;sort(pos+1,pos+n+1,cmp);
	for(int i=1;i<=n;i++)ss[ax[i]].insert({ay[i],i});
	for(int i=1;i<=cx[0];i++)if(ss[i].size())a[i]=(*ss[i].begin()).first;else a[i]=inf;
	// for(int i=1;i<=cx[0];i++)printf("%d ",a[i]);printf("\n");
	t1.build(1,1,cx[0]),t2.build(1,1,cy[0]-1);
	for(int i=1;i<=n;i++)
	{
		int x=pos[i];
		int l=1,r=bx[x]-1,pos=-1;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(t1.ask(1,mid,bx[x]-1)<by[x])pos=mid,l=mid+1;
			else r=mid-1;
		}
		if(pos==-1){printf("No\n");return 0;}
		auto it=--ss[pos].lower_bound({bx[x],0});ss[pos].erase(it);
		if(ss[pos].size())t1.change(1,pos,(*ss[pos].begin()).first);else t1.change(1,pos,inf);
		int y=(*it).second;
		mat[y]=x;
	}
	if(n==199996)return 0;
	// for(int i=1;i<=n;i++)printf("%d ",mat[i]);printf("\n");
	for(int i=1;i<=n;i++)in[ax[i]].push_back((abc){ay[i],by[mat[i]]-1,vv[i]}),out[bx[mat[i]]].push_back((abc){ay[i],by[mat[i]]-1,vv[i]});
	for(int i=1;i<=cx[0];i++)
	{
		// cout<<t2.t[5].val<<" "<<t2.t[5].col<<endl;
		sort(out[i].begin(),out[i].end(),cmp2);
		sort(in[i].begin(),in[i].end(),cmp1);
		for(auto j:out[i])
		{
			// cout<<j.l<<" "<<j.r<<" "<<j.v<<" "<<t2.ask(1,j.l,j.r).first<<" "<<t2.ask(1,j.l,j.r).second<<endl;
			if(!t2.ask(1,j.l,j.r).second){printf("No\n");return 0;}
			t2.change(1,j.l,j.r,j.v);
		}
		for(auto j:in[i])
		{
			// cout<<j.l<<" "<<j.r<<" "<<j.v<<" "<<t2.ask(1,j.l,j.r).first<<" "<<t2.ask(1,j.l,j.r).second<<endl;
			if(!t2.ask(1,j.l,j.r).second){printf("No\n");return 0;}
			t2.change(1,j.l,j.r,j.v);
		}
	}
	printf("Yes\n");
	for(int i=1;i<=n;i++)printf("%d\n",mat[i]);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 41492kb

input:

3
0 0
2 -2
1 1
2 2
3 1
2 3

output:

Yes
3
2
1

result:

ok answer is YES, 3 tokens

Test #2:

score: 0
Accepted
time: 3ms
memory: 41484kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 7ms
memory: 41352kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Runtime Error

input:

199996
94702923 895749121
-830347683 823853414
-638337012 -528381915
774504965 -903560893
465975432 931026841
47062323 901390864
539345338 830099354
278774201 896803047
-445303873 568413124
80473317 828648317
804283391 -307873779
543648687 893783688
814084625 -664894626
169476937 -999435847
-8232728...

output:


result: