QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423161#8179. 2D Parenthesesjr_linysWA 259ms27516kbC++142.7kb2024-05-27 21:21:202024-05-27 21:21:21

Judging History

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

  • [2024-05-27 21:21:21]
  • 评测
  • 测评结果:WA
  • 用时:259ms
  • 内存:27516kb
  • [2024-05-27 21:21:20]
  • 提交

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],g[N+5],h[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||(a.y==b.y&&a.x<b.x);});
	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].x-1,b[i].y};
		if(T.empty()){cout<<"No";return 0;}
		auto it=T.lower_bound(0);
		if(it==T.begin()){cout<<"No";return 0;}
		--it;
		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});
		g[lineCnt]=a[k].y;
		h[lineCnt]=b[i].y;
	}
	sort(v.begin(),v.end(),[](Line a,Line b){
		if(a.val!=b.val) return a.val<b.val;
		if((a.id>0)!=(b.id>0)) return a.id<b.id;
		if(a.id>0) return h[a.id]>h[b.id];
		return g[-a.id]>g[-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';
}

详细

Test #1:

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

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: 0ms
memory: 11868kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 2ms
memory: 9748kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

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

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