QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#398056 | #8179. 2D Parentheses | perekopska_d | WA | 364ms | 103084kb | C++14 | 5.6kb | 2024-04-24 21:37:13 | 2024-04-24 21:37:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ff first
#define ss second
#define pii pair <int, int>
#define el '\n'
#define pb push_back
#define mkp make_pair
const ll inf = 1e9 + 10;
const ll N = 2e5 + 50;
const ll LOG = 22;
const ll mod = 998244353;
struct pp {
int x;
int y;
bool f;
int id;
};
struct seg {
int y;
int l;
int r;
bool f;
};
int n, m, m2;
pp b[2 * N], a[2 * N];
multiset <int> st1[2 * N], st2[2 * N];
int ans[N], t1[8 * N], t2[8 * N];
vector <seg> v1, v2;
vector <int> xx, yy;
map <int, int> pos, pos2;
void full() {
for(int i = 0; i < 8 * N; i++) {
t1[i] = inf;
t2[i] = -inf;
}
}
bool comp(pp a, pp b) {
if(a.y != b.y) return a.y < b.y;
return a.x > b.x;
}
bool comp2(seg a, seg b) {
if(a.y != b.y) return a.y < b.y;
return a.f < b.f;
}
int get1(int i, int tl, int tr, int l, int r) {
if(tr < l || r < tl) return inf;
if(l <= tl && tr <= r) return t1[i];
int mid = (tl + tr) / 2;
return min(get1(i + i, tl, mid, l, r), get1(i + i + 1, mid + 1, tr, l, r));
}
int get2(int i, int tl, int tr, int l, int r) {
if(tr < l || r < tl) return -inf;
if(l <= tl && tr <= r) return t2[i];
int mid = (tl + tr) / 2;
return max(get2(i + i, tl, mid, l, r), get2(i + i + 1, mid + 1, tr, l, r));
}
void update1(int i, int tl, int tr, int pos, int val, int f) {
if(tl == tr) {
if(f) st1[tl].insert(val);
else st1[tl].erase(val);
if(st1[tl].size()) t1[i] = *st1[tl].begin();
else t1[i] = inf;
return;
}
int mid = (tl + tr) / 2;
if(pos <= mid) update1(i + i, tl, mid, pos, val, f);
else update1(i + i + 1, mid + 1, tr, pos, val, f);
t1[i] = min(t1[i + i], t1[i + i + 1]);
}
void update2(int i, int tl, int tr, int pos, int val, int f) {
if(tl == tr) {
if(f) st2[tl].insert(val);
else st2[tl].erase(val);
if(st2[tl].size()) {
auto it = st2[tl].end(); it--;
t2[i] = *it;
}
else t2[i] = -inf;
return;
}
int mid = (tl + tr) / 2;
if(pos <= mid) update2(i + i, tl, mid, pos, val, f);
else update2(i + i + 1, mid + 1, tr, pos, val, f);
t2[i] = max(t2[i + i], t2[i + i + 1]);
}
bool check_x(seg s) {
int r = lower_bound(xx.begin(), xx.end(), s.r) - xx.begin() - 1;
r = pos[xx[r]];
int l = upper_bound(xx.begin(), xx.end(), s.l) - xx.begin();
l = pos[xx[l]];
if(l > r) return 0;
if(get1(1, 1, m, l, r) < s.l) return 1;
if(get2(1, 1, m, l, r) > s.r) return 1;
return 0;
}
bool check_y(seg s) {
int r = lower_bound(yy.begin(), yy.end(), s.r) - yy.begin() - 1;
r = pos2[yy[r]];
int l = upper_bound(yy.begin(), yy.end(), s.l) - yy.begin();
l = pos2[yy[l]];
if(l > r) return 0;
if(get1(1, 1, m2, l, r) < s.l) return 1;
if(get2(1, 1, m2, l, r) > s.r) return 1;
return 0;
}
void upd_x(seg s) {
int i = pos[s.r];
update1(1, 1, m, i, s.l, s.f);
i = pos[s.l];
update2(1, 1, m, i, s.r, s.f);
}
void upd_y(seg s) {
int i = pos2[s.r];
update1(1, 1, m2, i, s.l, s.f);
i = pos2[s.l];
update2(1, 1, m2, i, s.r, s.f);
}
void solve() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> b[i].x >> b[i].y;
b[i].f = 1;
b[i].id = i;
xx.pb(b[i].x);
yy.pb(b[i].y);
}
for(int i = n; i < n + n; i++) {
cin >> b[i].x >> b[i].y;
b[i].f = 0;
b[i].id = i;
xx.pb(b[i].x);
yy.pb(b[i].y);
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
int cur = 1;
for(int i = 0; i < n + n; i++) {
if(i && xx[i - 1] != xx[i]) cur++;
pos[xx[i]] = cur;
m = cur;
}
cur = 1;
for(int i = 0; i < n + n; i++) {
if(i && yy[i - 1] != yy[i]) cur++;
pos2[yy[i]] = cur;
m2 = cur;
}
for(int i = 0; i < n + n; i++)
a[i] = b[i];
sort(a, a + n + n, comp);
set <pii> st;
for(int i = 0; i < n + n; i++) {
if(a[i].f) st.insert({a[i].x, a[i].id});
else {
auto it = st.lower_bound(mkp(a[i].x, 0));
if(it == st.begin()) return void(cout << "No");
it--;
pii j = *it; st.erase(it);
ans[j.ss] = a[i].id - n + 1;
v1.pb({b[j.ss].y, j.ff, a[i].x, 1});
v1.pb({a[i].y, j.ff, a[i].x, 0});
v2.pb({j.ff, b[j.ss].y, a[i].y, 1});
v2.pb({a[i].x, b[j.ss].y, a[i].y, 0});
}
}
sort(v1.begin(), v1.end(), comp2);
sort(v2.begin(), v2.end(), comp2);
full();
for(int i = 0; i < n + n; i++) {
int j = i;
while(j < n + n && v1[j].y == v1[i].y && !v1[j].f)
upd_x(v1[j]), j++;
while(j < n + n && v1[j].y == v1[i].y) {
if(check_x(v1[j])) return void(cout << "No");
upd_x(v1[j]); j++;
}
i = j - 1;
}
full();
for(int i = 0; i < n + n; i++) {
int j = i;
while(j < n + n && v2[j].y == v2[i].y && !v2[j].f)
upd_y(v2[j]), j++;
while(j < n + n && v2[j].y == v2[i].y) {
if(check_y(v2[j])) return void(cout << "No");
upd_y(v2[j]); j++;
}
i = j - 1;
}
cout << "Yes" << el;
for(int i = 0; i < n; i++)
cout << ans[i] << el;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 53900kb
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: 4ms
memory: 53596kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 11ms
memory: 41032kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 364ms
memory: 103084kb
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