QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422965#8179. 2D Parenthesesjr_linysWA 259ms26968kbC++142.4kb2024-05-27 20:33:252024-05-27 20:33:28

Judging History

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

  • [2024-05-27 20:33:28]
  • 评测
  • 测评结果:WA
  • 用时:259ms
  • 内存:26968kb
  • [2024-05-27 20:33:25]
  • 提交

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,un[N*2+5],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].y<a[v].y||(a[u].y==a[v].y&&a[u].x<a[v].x);
	}
};
set<int,cmp> T;
int t[N*8],ta[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(){
	{//预处理
		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.x<b.x;});
	sort(b+1,b+1+n,[](Dot a,Dot b){return a.x<b.x||(a.x==b.x&&a.y<b.y);});
	for(int i=1,j=1;i<=n;++i){
		while(j<=n&&a[j].x<b[i].x) T.insert(j),++j;
		a[0]=b[i];
		if(T.empty()){printf("No"); return 0;}
		auto it=--T.upper_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: 0ms
memory: 9796kb

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: 1ms
memory: 9836kb

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 259ms
memory: 26968kb

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 answer expected YES, found NO