QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423287 | #8179. 2D Parentheses | Vanilla_QwQ | WA | 171ms | 18604kb | C++14 | 2.7kb | 2024-05-27 22:05:26 | 2024-05-27 22:05:35 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#define LL long long
#define il inline
#define Pii pair<int, int>
#define fir first
#define sec second
#define SIZ(x) int(x.size())
#define ALL(x) x.begin(), x.end()
using namespace std;
const int MaxN = 2e5 + 3;
int N;
struct node{
int x, y, id;
bool operator < (const node &b) const {
if(y == b.y) return x < b.x;
return y < b.y;
}
bool operator > (const node &b) const {
return b < *this;
}
} a[MaxN], b[MaxN];
set<Pii> st;
struct seg{
int y, l, r, id, typ, ano_y;
} o[MaxN*2];
int c[MaxN];
il bool check(){
multiset<int> st;
sort(a+1, a+N+1, [&](const node &x, const node &y){
return x.id < y.id;
});
sort(b+1, b+N+1, [&](const node &x, const node &y){
return x.id < y.id;
});
int m = 0;
for(int i = 1; i <= N; i++){
auto &d = b[c[a[i].id]];
o[++m] = {a[i].y, a[i].x, d.x, i, 1, 0};
o[++m] = {d.y, a[i].x, d.x, i, -1, a[i].y};
}
sort(o+1, o+m+1, [&](const seg &a, const seg &b){
if(a.y != b.y) return a.y < b.y;
if(a.typ != b.typ) return a.typ > b.typ;
if(a.typ == -1 && b.typ == -1) return a.ano_y > b.ano_y;
});
// for(int i = 1; i <= m; i++){
// cerr<<o[i].y<<' '<<o[i].l<<' '<<o[i].r<<' '<<o[i].id<<' '<<o[i].typ<<' '<<o[i].ano_y<<endl;
// }
for(int i = 1; i <= m; i++){
auto &sg = o[i];
int l = sg.l, r = sg.r;
if(sg.typ == 1){
auto it = st.upper_bound(l);
if(it != st.end() && *it < r) return false;
st.insert(l), st.insert(r);
}
else {
auto it = st.upper_bound(l);
if(it != st.end() && *it < r) return false;
st.erase(st.find(l)), st.erase(st.find(r));
}
}
return true;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0);
cin>>N;
for(int i = 1, x, y; i <= N; i++) cin>>x>>y, a[i] = {x, y, i};
for(int i = 1, x, y; i <= N; i++) cin>>x>>y, b[i] = {x, y, i};
sort(a+1, a+N+1, less<>());
sort(b+1, b+N+1, greater<>());
for(int i = N, j = 0; i >= 1; i--) {
while(j+1 <= N && b[j+1].y > a[i].y) j++, st.insert({b[j].x, b[j].id});
// cerr<<i<<": "<<SIZ(st)<<endl;
auto it = st.lower_bound({a[i].x, -1});
if(it == st.end()){
cout<<"No"<<'\n';
return 0;
}
c[a[i].id] = it->sec;
st.erase(it);
}
// cerr<<"?"<<endl;
// for(int i = 1; i <= N; i++) cerr<<c[i]<<'\n';
if(check()){
cout<<"Yes"<<'\n';
for(int i = 1; i <= N; i++) cout<<c[i]<<'\n';
}
else cout<<"No"<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7712kb
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: 1ms
memory: 7944kb
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: 7864kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 171ms
memory: 18604kb
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