QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#422787#8179. 2D ParenthesesEnder_PeachWA 151ms50932kbC++142.2kb2024-05-27 19:19:572024-05-27 19:19:57

Judging History

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

  • [2024-05-27 19:19:57]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:50932kb
  • [2024-05-27 19:19:57]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=4e5+7,K=63;
struct nod { ll x,y,t,p; } a[N*2];
struct mat { ll xa,ya,xb,yb; } b[N],c[N*2];
ll n,mch[N*2],ans[N],m;
set<pair<pll,ll>> s;
struct sgt {
	ll t[N*K],tl[N*K],tr[N*K],cnn,rt;
	void pup(ll p) { t[p]=t[tl[p]]+t[tr[p]]; }
	void add(ll x,ll z,ll &p,ll l=-I,ll r=I) {
		if (!p) p=++cnn;
		if (l==r) return t[p]+=z,void();
		ll mid=l+r>>1;
		if (x<=mid) add(x,z,tl[p],l,mid);
		else add(x,z,tr[p],mid+1,r);
		pup(p);
	}
	ll que(ll x,ll y,ll p,ll l=-I,ll r=I) {
		if (!p||x>y) return 0;
		if (x<=l&&r<=y) return t[p];
		ll mid=l+r>>1,ret=0;
		if (x<=mid) ret=que(x,y,tl[p],l,mid);
		if (y>mid) ret+=que(x,y,tr[p],mid+1,r);
		return ret;
	}
} T;
void mian() {
	scanf("%lld",&n);
	for (ll i=1;i<=n*2;i++) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].t=i>n,a[i].p=(i-1)%n+1;
	sort(a+1,a+n*2+1,[](nod x,nod y){return x.x<y.x;});
	for (ll l=1,r;l<=n*2;l=r+1) {
		for (r=l;r<n*2&&a[r+1].x==a[l].x;r++);
		for (ll i=l;i<=r;i++) if (a[i].t==1) {
			auto it=s.lower_bound({{a[i].y,-J},0});
			if (it==s.begin()) return cout<<"No",void();
			it--; auto x=*it;
			mch[i]=x.se,s.erase(it);
		}
		for (ll i=l;i<=r;i++) if (a[i].t==0) s.insert({{a[i].y,-a[i].x},i});
	}
	for (ll i=1;i<=n*2;i++) if (a[i].t==1)
		assert(mch[i]),assert(a[mch[i]].x<a[i].x),assert(a[mch[i]].y<a[i].y),
		ans[a[mch[i]].p]=a[i].p,b[a[i].p]={a[mch[i]].x,a[mch[i]].y,a[i].x,a[i].y};
	for (ll i=1;i<=n;i++) c[++m]={b[i].xa,b[i].ya,0,b[i].yb},c[++m]={b[i].xb,b[i].ya,1,b[i].yb};
	sort(c+1,c+m+1,[](mat x,mat y){return x.xa!=y.xa?x.xa<y.xa:x.xb>y.xb;});
	for (ll i=1;i<=m;i++) {
		if (c[i].xb==0) {
			if (T.que(c[i].ya+1,c[i].yb-1,T.rt)) return cout<<"No",void();
			T.add(c[i].ya,1,T.rt),T.add(c[i].yb,1,T.rt);
		}
		else T.add(c[i].ya,-1,T.rt),T.add(c[i].yb,-1,T.rt);
	}
	cout<<"Yes\n";
	for (ll i=1;i<=n;i++) cout<<ans[i]<<"\n";
}
bool ORY; int main() {
//	while (1)
//	int t; for (scanf("%d",&t);t--;)
    mian();
    cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB "<<clock()<<"ms";
    return 0;
}

详细

Test #1:

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

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

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 151ms
memory: 50932kb

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