QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423045#8179. 2D Parenthesesjr_linysWA 246ms20816kbC++142.5kb2024-05-27 20:53:332024-05-27 20:53:34

Judging History

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

  • [2024-05-27 20:53:34]
  • 评测
  • 测评结果:WA
  • 用时:246ms
  • 内存:20816kb
  • [2024-05-27 20:53:33]
  • 提交

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});
	}
	if(n<=100){
		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: 1ms
memory: 9852kb

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

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 246ms
memory: 20816kb

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:

Yes
82079
143937
36911
23912
29196
103293
198434
65913
157367
48765
41010
148908
80650
146103
196489
99283
116023
160688
141927
99488
40423
87997
59175
165032
163355
57765
97472
31857
150106
185365
76890
97333
118296
142517
154996
163892
142018
1988
54877
191396
65560
70618
199137
56352
183975
16401...

result:

wrong answer 1st words differ - expected: '21701', found: '82079'