QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422523 | #8179. 2D Parentheses | Ender_Peach | WA | 168ms | 39824kb | C++14 | 2.1kb | 2024-05-27 15:31:07 | 2024-05-27 15:31:08 |
Judging History
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=2e5+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?x.x<y.x:x.y<y.y;});
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.upper_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)
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
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: 3880kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 168ms
memory: 39824kb
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