QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423120 | #8179. 2D Parentheses | jr_linys | WA | 258ms | 24480kb | C++14 | 2.6kb | 2024-05-27 21:11:21 | 2024-05-27 21:11:22 |
Judging History
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||(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});
}
sort(v.begin(),v.end(),[](Line a,Line b){
if(a.val!=b.val) return a.val<b.val;
if(a.id%2!=b.id%2) return a.id<b.id;
if(a.id>0) return a.r-a.l>b.r-b.l;
return a.r-a.l<b.r-b.l;
});
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: 9876kb
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: 9844kb
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: 9744kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 258ms
memory: 24480kb
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