QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423045 | #8179. 2D Parentheses | jr_linys | WA | 246ms | 20816kb | C++14 | 2.5kb | 2024-05-27 20:53:33 | 2024-05-27 20:53:34 |
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;});
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'