QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424006#8179. 2D ParenthesesYMH_fourteenWA 1ms7660kbC++143.0kb2024-05-28 20:44:232024-05-28 20:44:23

Judging History

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

  • [2024-05-28 20:44:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7660kb
  • [2024-05-28 20:44:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "E:/OI/normal/templates/debug.h"
#else
#define dbg(...) (void)0
#define msg(...) (void)0
#endif
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=200005;
int n;
struct poi
{
	int x,y,id;
}lef[N],rig[N];
bool cmp1(poi &x,poi &y)
{
	return x.y==y.y?x.x<y.x:x.y<y.y;
}
bool cmp2(poi &x,poi &y)
{
	return x.x==y.x?x.y<y.y:x.x<y.x;
}
int ans[N];
struct op
{
	int tim,l,r,typ,lst;
	bool add;
	bool operator<(const op &rhs)const
	{
		if(tim!=rhs.tim)return tim<rhs.tim;
		if(add!=rhs.add)return add<rhs.add;// delete first
		if(add)return r-l+1>rhs.r-rhs.l+1; // add larger ones first
		return r-l+1<rhs.r-rhs.l+1;		   // remove smaller ones first
	}
}f[N<<1];
struct cr
{
	bool isr;
	int cor,id;
	bool operator<(const cr &rhs)const
	{
		if(cor!=rhs.cor)return cor<rhs.cor;
		if(isr^rhs.isr)return isr; 
		if(isr)return id>rhs.id;
		return id<rhs.id;
	}
};
vector<cr>coor;
struct fajlkdjfklsad{bool operator()(poi x,poi y){return cmp2(x,y);}};

set<int>st2;
int tmp[N];

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n;
	for(int i=1;i<=n;i++)cin>>lef[i].x>>lef[i].y,lef[i].id=i;
	for(int i=1;i<=n;i++)cin>>rig[i].x>>rig[i].y,rig[i].id=i;
	sort(lef+1,lef+n+1,cmp1);
	sort(rig+1,rig+n+1,cmp1);
	set<poi,fajlkdjfklsad>st;
	for(int i=1,j=1;i<=n;i++)
	{
		while(j<=n&&lef[j].y<rig[i].y)st.insert(lef[j++]);
		auto it=st.upper_bound(poi{rig[i].x-1,INT_MAX,-114514});
		if(it==st.begin())return puts("No"),0;
		it--;
		ans[it->id]=rig[i].id;
		f[2*i-1]={it->x,it->y,rig[i].y,i,1},f[2*i]={rig[i].x,it->y,rig[i].y,i,0};
		st.erase(it);
	}
	sort(f+1,f+(n<<1)+1);
//	for(int i=1;i<=n<<1;i++)cerr<<f[i].add<<" "<<f[i].l<<" "<<f[i].r<<endl;
	for(int i=1;i<=n<<1;i++)
		if(f[i].add)coor.PB(cr{0,f[i].l,i}),coor.PB(cr{1,f[i].r,i}),tmp[f[i].typ]=i;
	sort(ALL(coor));
//	for(auto i:coor)cerr<<i.isr<<" "<<i.cor<<" "<<i.id<<endl;
	for(int i=1;i<=n<<1;i++)
		f[i].l=lower_bound(ALL(coor),cr{0,f[i].l,tmp[f[i].typ]})-coor.begin()+1,
		f[i].r=lower_bound(ALL(coor),cr{1,f[i].r,tmp[f[i].typ]})-coor.begin()+1;
//	for(int i=1;i<=n<<1;i++)cerr<<f[i].add<<" "<<f[i].l<<" "<<f[i].r<<endl;
	for(int i=1;i<=n<<1;i++)
		if(f[i].add)
		{
			auto itl=st2.lower_bound(f[i].l),itr=st2.lower_bound(f[i].r);
			if(itl!=itr)return puts("No"),0;
			st2.insert(f[i].l),st2.insert(f[i].r);
		}
		else st2.erase(f[i].l),st2.erase(f[i].r);
//	st.clear();
	for(int i=n<<1;i;i--)
		if(!f[i].add)
		{
			auto itl=st2.lower_bound(f[i].l),itr=st2.lower_bound(f[i].r);
			if(itl!=itr)return puts("No"),0;
			st2.insert(f[i].l),st2.insert(f[i].r);
		}
		else st2.erase(f[i].l),st2.erase(f[i].r);
	cout<<"Yes\n";
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 7660kb

input:

2
1 0
0 1
2 3
3 2

output:

Yes
2
1

result:

wrong answer expected NO, found YES