QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423967 | #8179. 2D Parentheses | CharlieVinnie | RE | 0ms | 3732kb | C++20 | 2.8kb | 2024-05-28 20:14:03 | 2024-05-28 20:14:04 |
Judging History
answer
#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define fi first
#define se second
using namespace std; typedef long long ll;
constexpr int N=4e5+5; using pii = pair<int,int>; using tiii = tuple<int,int,int>;
int MERGE(int x,int y) { if(x==-1||y==-1) return -1;; if(x==0||y==0) return x^y;; if(x==y) return x; else return -1; }
class STree{
int n,a[N];
public:
void init(int _n) { n=_n; }
void modify(int l,int r,int x) { For(i,l,r) a[i]=x; }
int query(int l,int r) { int res=0; For(i,l,r) res=MERGE(res,a[i]);; return res; }
}T;
void Discrete(int* a,int n,int* tmp,int& tcnt){
tcnt=0; For(i,1,n) tmp[++tcnt]=a[i];
sort(tmp+1,tmp+1+tcnt); tcnt=unique(tmp+1,tmp+1+tcnt)-(tmp+1);
For(i,1,n) a[i]=lower_bound(tmp+1,tmp+1+tcnt,a[i])-tmp;
}
int n,X[N],Y[N],tmpx[N],tcntx,tmpy[N],tcnty,ans[N],tot,fa[N]; vector<pii> lis[N][2]; struct Op { int l,r,id; }; vector<Op> add[N],del[N];
[[noreturn]] void NO() { cout<<"No\n"; exit(1); }
void Add(int u,int v){
debug(u,v);
assert(u<=n&&v>n&&X[u]<X[v]&&Y[u]<Y[v]);
ans[u]=v-n; tot++;
add[X[u] ].emplace_back(Op{Y[u],Y[v]-1,tot});
del[X[v]-1].emplace_back(Op{Y[u],Y[v]-1,tot});
}
signed main(){
atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
cin>>n; For(i,1,n*2) cin>>X[i]>>Y[i];
Discrete(X,n*2,tmpx,tcntx), Discrete(Y,n*2,tmpy,tcnty);
For(i,1,n*2) lis[X[i]][i>n].emplace_back(Y[i],i);
multiset<tiii> S;
For(i,1,tcntx){
for(auto [y,id]:lis[i][1]){
auto it=S.lower_bound(tiii(y,0,0));
if(it==S.begin()) NO();
int o=get<2>(*--it);
Add(o,id);
S.erase(it);
}
for(auto [y,id]:lis[i][0]) S.emplace(y,-i,id);
}
T.init(tcnty-1);
For(i,1,tcntx){
sort(add[i].begin(),add[i].end(),[](Op A,Op B){return pii(A.r-A.l,A.id)>pii(B.r-B.l,B.id);});
sort(del[i].begin(),del[i].end(),[](Op A,Op B){return pii(A.r-A.l,A.id)<pii(B.r-B.l,B.id);});
for(auto [l,r,id]:add[i]){
debug(i,l,r,id);
int c=T.query(l,r); if(c==-1) NO();
fa[id]=c; T.modify(l,r,id);
}
for(auto [l,r,id]:del[i]){
debug(i,l,r,id);
int c=T.query(l,r);if(c!=id) NO();
T.modify(l,r,fa[id]);
}
}
cout<<"Yes\n"; For(i,1,n) cout<<ans[i]<<'\n';
return 0;
}
// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// Started Coding On: May 27 Mon, 20 : 55 : 45
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
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: -100
Runtime Error
input:
2 1 0 0 1 2 3 3 2
output:
No