QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#464850 | #8179. 2D Parentheses | ucup-team052 | WA | 301ms | 31024kb | C++14 | 3.3kb | 2024-07-06 15:25:19 | 2024-07-06 15:25:20 |
Judging History
answer
#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=400005,INF=0X3F3F3F3F;
int n,ans[N];
vector<int>vx,vy;
struct node{
int x,y,id;
}a[N];
struct cmp{
bool operator()(const int&x,const int&y)const{
if(a[x].x!=a[y].x)return a[x].x<a[y].x;
if(a[x].y!=a[y].y)return a[x].y<a[y].y;
return x<y;
}
};
vector<tuple<int,int,int> >vec[N];
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
rd(n);
rep(i,1,n){
rd(a[i].x),rd(a[i].y),a[i].id=i;
}
rep(i,n+1,n+n){
rd(a[i].x),rd(a[i].y),a[i].id=i;
}
rep(i,1,n+n)vx.pb(a[i].x),vy.pb(a[i].y);
sort(vx.begin(),vx.end()),vx.erase(unique(vx.begin(),vx.end()),vx.end());
sort(vy.begin(),vy.end()),vy.erase(unique(vy.begin(),vy.end()),vy.end());
rep(i,1,n+n){
a[i].x=lower_bound(vx.begin(),vx.end(),a[i].x)-vx.begin()+1;
a[i].y=lower_bound(vy.begin(),vy.end(),a[i].y)-vy.begin()+1;
}
sort(a+1,a+n+n+1,[&](node u,node v){return u.y!=v.y?u.y<v.y:u.x<v.x;});
set<int,cmp>S;
for(int i=1,j;i<=n+n;i=j){
j=i+1;
while(j<=n+n&&a[i].y==a[j].y)++j;
rep(k,i,j-1)if(a[k].id>n){
a[0].x=a[k].x;
a[0].y=~INF;
auto it=S.lower_bound(0);
if(it!=S.begin()){
--it;
node u=a[*it];
ans[u.id]=a[k].id-n;
S.erase(it);
}else{
puts("No");
exit(0);
}
}
rep(k,i,j-1)if(a[k].id<=n){
S.insert(k);
}
}
sort(a+1,a+n+n+1,[&](node lhs,node rhs){return lhs.id<rhs.id;});
rep(i,1,n){
vec[a[i].x].eb(a[i].y,a[ans[i]+n].y,1);
vec[a[ans[i]+n].x].eb(a[i].y,a[ans[i]+n].y,-1);
}
multiset<int>T;
rep(x,1,SZ(vx)){
for(auto&u:vec[x]){
if(get<2>(u)==1){
T.insert(get<0>(u));
T.insert(get<1>(u));
}else{
T.erase(T.find(get<0>(u)));
T.erase(T.find(get<1>(u)));
}
}
for(auto&u:vec[x]){
if(get<2>(u)==1){
auto it=T.upper_bound(get<0>(u));
if(it!=T.end()&&*it<get<1>(u)){
puts("No");
exit(0);
}
}
}
}
rep(i,1,n+n){
swap(a[i].x,a[i].y);
}
T.clear();
rep(i,1,n+n)vec[i].clear();
rep(i,1,n){
vec[a[i].x].eb(a[i].y,a[ans[i]+n].y,1);
vec[a[ans[i]+n].x].eb(a[i].y,a[ans[i]+n].y,-1);
}
rep(x,1,SZ(vy)){
for(auto&u:vec[x]){
if(get<2>(u)==1){
T.insert(get<0>(u));
T.insert(get<1>(u));
}else{
T.erase(T.find(get<0>(u)));
T.erase(T.find(get<1>(u)));
}
}
for(auto&u:vec[x]){
if(get<2>(u)==1){
auto it=T.upper_bound(get<0>(u));
if(it!=T.end()&&*it<get<1>(u)){
puts("No");
exit(0);
}
}
}
}
puts("Yes");
rep(i,1,n)printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13580kb
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: 16624kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 4ms
memory: 16628kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 301ms
memory: 31024kb
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