QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#423984 | #8179. 2D Parentheses | CharlieVinnie | WA | 443ms | 58016kb | C++20 | 3.8kb | 2024-05-28 20:28:37 | 2024-05-28 20:28:37 |
Judging History
answer
// #define _GLIBCXX_DEBUG
#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;
class STree{
int n,O[N<<2],tag[N<<2];
#define k1 (k<<1)
#define k2 (k<<1|1)
void setg(int k,int x) { tag[k]=O[k]=x; }
void pushdown(int k) { if(tag[k]) setg(k1,tag[k]),setg(k2,tag[k]),tag[k]=0; }
void modify(int k,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr) return setg(k,x),void();
int mid=(l+r)>>1; pushdown(k);
if(ql<=mid) modify(k1,l,mid,ql,qr,x);
if(mid+1<=qr) modify(k2,mid+1,r,ql,qr,x);
O[k]=MERGE(O[k1],O[k2]);
}
int query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return O[k];
int mid=(l+r)>>1,res=0; pushdown(k);
if(ql<=mid) res=MERGE(res,query(k1,l,mid,ql,qr));
if(mid+1<=qr) res=MERGE(res,query(k2,mid+1,r,ql,qr));
return res;
}
public:
void init(int _n) { n=_n; }
void modify(int l,int r,int x) { modify(1,1,n,l,r,x); }
int query(int l,int r) { return query(1,1,n,l,r); }
}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(0); }
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-1,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
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 16200kb
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: 15856kb
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: 13804kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 443ms
memory: 58016kb
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