QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423040#8179. 2D Parenthesesjr_linysWA 2ms9784kbC++142.4kb2024-05-27 20:52:512024-05-27 20:52:51

Judging History

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

  • [2024-05-27 20:52:51]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9784kb
  • [2024-05-27 20:52:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T=int> T read(){
	char c;bool f=1;
	while(!isdigit(c=getchar())) if(c=='-') f=0;
	T x=c^'0';
	while(isdigit(c=getchar())) x=x*10+(c^'0');
	return f?x:-x;
}
template<class T>void Min(T &a,T b){if(b<a) a=b;}
template<class T>void Max(T &a,T b){if(b>a) a=b;}
const int N=200000;
int n,ans[N+5];
struct Dot{
	int x,y,id;
}a[N+5],b[N+5];
struct cmp{
	bool operator()(int u,int v)const{
		return a[u].x<a[v].x||(a[u].x==a[v].x&&a[u].y<a[v].y);
	}
};
set<int,cmp> T;
unsigned int t[N*8],ta[N*8];
bool vis[N*8];
inline void pushup(int p){
	t[p]=max(t[p<<1],t[p<<1|1])+ta[p];
}
void upd(int p,int l,int r,int x,int y,int d){
	if(x<=l&&r<=y) return t[p]+=d,ta[p]+=d,void();
	int mid=(l+r)>>1;
	if(x<=mid) upd(p<<1,l,mid,x,y,d);
	if(y>mid) upd(p<<1|1,mid+1,r,x,y,d);
	pushup(p);
}
int qry(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y) return t[p];
	int mid=(l+r)>>1,ans=0;
	if(x<=mid) Max(ans,qry(p<<1,l,mid,x,y));
	if(y>mid) Max(ans,qry(p<<1|1,mid+1,r,x,y));
	return ans+ta[p];
}
int lineCnt,w[N+5];
struct Line{
	int l,r,val,id;
};
vector<Line> v;

signed main(){
	{//预处理
		static int un[N*2+5];
		n=read();
		for(int i=1;i<=n;++i) a[i]={read(),read(),i};
		for(int i=1;i<=n;++i) b[i]={read(),read(),i};
		auto get=[](int &x){x=lower_bound(un+1,un+1+n*2,x)-un;};
		for(int i=1;i<=n;++i) un[i]=a[i].x,un[i+n]=b[i].x;
		sort(un+1,un+1+n*2);
		for(int i=1;i<=n;++i) get(a[i].x),get(b[i].x);
		for(int i=1;i<=n;++i) un[i]=a[i].y,un[i+n]=b[i].y;
		sort(un+1,un+1+n*2);
		for(int i=1;i<=n;++i) get(a[i].y),get(b[i].y);
	}
	sort(a+1,a+1+n,[](Dot a,Dot b){return a.y<b.y;});
	sort(b+1,b+1+n,[](Dot a,Dot b){return a.y<b.y||(a.y==b.y&&a.x<b.x);});
	for(int i=1,j=1;i<=n;++i){
		while(j<=n&&a[j].y<b[i].y) T.insert(j),++j;
		a[0]=b[i];
		if(T.empty()){printf("No"); return 0;}
		auto it=--T.lower_bound(0);
		int k=*it;T.erase(it);
		ans[a[k].id]=b[i].id;
		++lineCnt;
		v.push_back({a[k].x,b[i].x-1,a[k].y,lineCnt});
		v.push_back({a[k].x,b[i].x-1,b[i].y,-lineCnt});
	}/*
	sort(v.begin(),v.end(),[](Line a,Line b){return a.val<b.val||(a.val==b.val&&a.id<b.id);});
	for(auto [l,r,val,id]:v){
		if(id>0){
			w[id]=qry(1,1,n*2,l,r);
			upd(1,1,n*2,l,r,1);
		}else{
			upd(1,1,n*2,l,r,-1);
			if(qry(1,1,n*2,l,r)!=w[-id]){cout<<"No";return 0;}
		}
	}*/
	cout<<"Yes\n";
	for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9784kb

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: 9768kb

input:

2
1 0
0 1
2 3
3 2

output:

Yes
2
1

result:

wrong answer expected NO, found YES