QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423251#8179. 2D ParenthesesXun_xiaoyaoWA 255ms15440kbC++144.3kb2024-05-27 21:50:422024-05-27 21:50:42

Judging History

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

  • [2024-05-27 21:50:42]
  • 评测
  • 测评结果:WA
  • 用时:255ms
  • 内存:15440kb
  • [2024-05-27 21:50:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int Qread()
{
	int x=0;bool f=false;char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return f?-x:x;
}
typedef pair<int,int> pr;
int n,bk1[200010],bk2[200010];
pr p1[200010],p2[200010];
int X[400010],Y[400010],totx,toty;
int fl1,fl2;
int pp[200010],p_[200010],fa[200010];

#define ls (pos<<1)
#define rs (pos<<1|1)
#define mid (l+r>>1)
int s[2000010],mx[200010],mn[200010];
void pushdown(int pos){if(s[pos]) mx[ls]=mn[ls]=s[ls]=mx[rs]=mn[rs]=s[rs]=s[pos],s[pos]=0;}
void update(int pos){mx[pos]=max(mx[ls],mx[rs]),mn[pos]=min(mn[ls],mn[rs]);}
int get_nd(int x,int pos=1,int l=1,int r=toty)
{
	if(l==r) return s[pos];
	if(x<=mid) return pushdown(pos),get_nd(x,ls,l,mid);
	else return pushdown(pos),get_nd(x,rs,mid+1,r);
}
void range_change(int L,int R,int x,int pos=1,int l=1,int r=toty)
{
	if(L<=l&&r<=R) return s[pos]=x,void();
	if(r<L||R<l) return;
	return pushdown(pos),range_change(L,R,x,ls,l,mid),range_change(L,R,x,rs,mid+1,r),update(pos);
}
int range_max(int L,int R,int pos=1,int l=1,int r=toty)
{
	if(L<=l&&r<=R) return mx[pos];
	if(r<L||R<l) return -20070610;
	else return pushdown(pos),max(range_max(L,R,ls,l,mid),range_max(L,R,rs,mid+1,r));
}
int range_min(int L,int R,int pos=1,int l=1,int r=toty)
{
	if(L<=l&&r<=R) return mn[pos];
	if(r<L||R<l) return 20070610;
	else return pushdown(pos),min(range_min(L,R,ls,l,mid),range_min(L,R,rs,mid+1,r));
}
void show(int pos=1,int l=1,int r=toty)
{
	if(l==r) printf("%d ",s[pos]);
	else pushdown(pos),show(ls,l,mid),show(rs,mid+1,r);
}
#undef ls
#undef rs
#undef mid

#define x first
#define y second
struct Node{pr loc;int id;};
bool operator<(Node A,Node B)
{
	if(A.loc.y!=B.loc.y) return A.loc.y<B.loc.y;
	if(A.loc.x!=B.loc.x) return A.loc.x<B.loc.x;
	return false;
}
set<Node> S;set<Node>::iterator it;
int main()
{
	n=Qread();
	for(int i=1;i<=n;i++) p1[i].x=Qread(),p1[i].y=Qread();
	for(int i=1;i<=n;i++) p2[i].x=Qread(),p2[i].y=Qread();

	for(int i=1;i<=n;i++) X[++totx]=p1[i].x,Y[++toty]=p1[i].y;
	for(int i=1;i<=n;i++) X[++totx]=p2[i].x,Y[++toty]=p2[i].y;

	sort(X+1,X+totx+1);totx=unique(X+1,X+totx+1)-X-1;
	sort(Y+1,Y+toty+1);toty=unique(Y+1,Y+toty+1)-Y-1;

	for(int i=1;i<=n;i++) p1[i].x=lower_bound(X+1,X+totx+1,p1[i].x)-X,p1[i].y=lower_bound(Y+1,Y+toty+1,p1[i].y)-Y;
	for(int i=1;i<=n;i++) p2[i].x=lower_bound(X+1,X+totx+1,p2[i].x)-X,p2[i].y=lower_bound(Y+1,Y+toty+1,p2[i].y)-Y;

	// for(int i=1;i<=n;i++) printf("(%d %d)",p1[i].x,p1[i].y);printf("\n");
	// for(int i=1;i<=n;i++) printf("(%d %d)",p2[i].x,p2[i].y);printf("\n");

	for(int i=1;i<=n;i++) bk2[i]=i;
	sort(bk2+1,bk2+n+1,[&](int a,int b){return p1[a]<p1[b];});
	for(int i=1;i<=n;i++) bk1[bk2[i]]=i;
	sort(bk2+1,bk2+n+1,[&](int a,int b){return p2[a]<p2[b];});
	sort(p1+1,p1+n+1),sort(p2+1,p2+n+1);

	// for(int i=1;i<=n;i++) printf("(%d %d)",p1[i].x,p1[i].y);printf("\n");
	// for(int i=1;i<=n;i++) printf("(%d %d)",p2[i].x,p2[i].y);printf("\n");

	fl1=fl2=1;
	while(fl1<=n&&fl2<=n)
	{
		if(p2[fl2].x<=p1[fl1].x)
		{
			it=S.lower_bound(Node{make_pair(0,p2[fl2].y),fl2});
			if(it==S.begin()) return printf("No\n"),0;
			it--;
			pp[it->id]=fl2,p_[fl2]=it->id;S.erase(it);
			fl2++;
		}
		else S.insert(Node{p1[fl1],fl1}),fl1++;
	}
	if(fl1<=n) return printf("No\n"),0;
	while(fl2<=n)
	{
		it=S.lower_bound(Node{make_pair(0,p2[fl2].y),fl2});
		if(it==S.begin()) return printf("No\n"),0;
		it--;
		pp[it->id]=fl2;S.erase(it);
		fl2++;
	}
	
	// for(int i=1;i<=n;i++) printf("[%d %d]*[%d %d]\n",p1[i].x,p2[pp[i]].x,p1[i].y,p2[pp[i]].y);

	if(n>=1000) printf("--------\n");

	fl1=fl2=1;
	int tl,tr;
	while(fl1<=n&&fl2<=n)
	{
		if(p2[fl2].x<=p1[fl1].x)
		{
			range_change(p1[p_[fl2]].y,p2[fl2].y-1,fa[p_[fl2]]);
			fl2++;
		}
		else
		{
			tl=get_nd(p1[fl1].y),tr=get_nd(p2[pp[fl1]].y-1);
			if(tl!=tr||range_max(p1[fl1].y,p2[pp[fl1]].y-1)!=range_min(p1[fl1].y,p2[pp[fl1]].y-1)) return printf("No\n"),0;
			if(tl&&p2[pp[fl1]].x>p2[pp[tl]].x) return printf("No\n"),0;
			range_change(p1[fl1].y,p2[pp[fl1]].y-1,fl1);
			fa[fl1]=tl;
			fl1++;
		}

		// printf("%d %d:\n",fl1,fl2);
		// show();printf("\n");
	}

	printf("Yes\n");
	for(int i=1;i<=n;i++) printf("%d\n",bk2[pp[bk1[i]]]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11960kb

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: 2ms
memory: 11980kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 1ms
memory: 9788kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 255ms
memory: 15440kb

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:

--------
No

result:

wrong output format YES or NO expected, but -------- found