This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
struct Q {
int t, x, y;
};
const int N = 2e6 + 5, INF = 1e9;
set<pair<int, int>> st[N * 4];
vector<pair<int, int>> pts;
vector<Q> qrs;
bool used[N];
vector<int> vx, pts_to_add;
int lc[N], rc[N], mn_x[N], mn_y[N], up_x[N], up_y[N], sz[N], anc[N], pr[N];
pair<int, int> val[N];
int cv = 1;
bool is_earlier(pair<int, int> &a, pair<int, int> &b) {
return a.first == b.first ? a.second > b.second : a.first < b.first;
}
void get_pts_to_add(int x, int y, int v = 1, int L = 0, int R = vx.size() - 1) {
if (L > x)
return;
if (R <= x) {
while (!st[v].empty() &&
st[v].begin()->first <= y) {
int x = st[v].begin()->second;
st[v].erase(st[v].begin());
if (!used[x]) {
used[x] = true;
pts_to_add.push_back(x);
}
}
}
else {
int m = (L + R) >> 1;
get_pts_to_add(x, y, v * 2, L, m);
get_pts_to_add(x, y, v * 2 + 1, m + 1, R);
}
}
void add_pt(int x, pair<int, int> y, int v = 1, int L = 0, int R = vx.size() - 1) {
st[v].insert(y);
if (L != R) {
int m = (L + R) >> 1;
if (x <= m)
add_pt(x, y, v * 2, L, m);
else
add_pt(x, y, v * 2 + 1, m + 1, R);
}
}
void push(int v) {
if (v == 0)
return;
if (up_x[v]) {
up_x[lc[v]] = up_x[v];
up_x[rc[v]] = up_x[v];
val[v].first = up_x[v];
mn_x[v] = up_x[v];
up_x[v] = 0;
}
if (up_y[v]) {
up_y[lc[v]] = up_y[v];
up_y[rc[v]] = up_y[v];
val[v].second = up_y[v];
mn_y[v] = up_y[v];
up_y[v] = 0;
}
}
void upd(int v) {
sz[v] = sz[lc[v]] + sz[rc[v]] + 1;
mn_x[v] = val[v].first;
mn_y[v] = val[v].second;
if (lc[v] != 0) {
mn_x[v] = min(mn_x[lc[v]], mn_x[v]);
mn_y[v] = min(mn_y[lc[v]], mn_y[v]);
}
if (rc[v] != 0) {
mn_x[v] = min(mn_x[rc[v]], mn_x[v]);
mn_y[v] = min(mn_y[rc[v]], mn_y[v]);
}
anc[lc[v]] = v;
anc[rc[v]] = v;
}
pair<int, int> split(int v, pair<int, int> k) {
if (v == 0)
return {0, 0};
push(v);
push(lc[v]);
push(rc[v]);
if (is_earlier(val[v], k)) {
auto p = split(rc[v], k);
rc[v] = p.first;
upd(v);
anc[v] = 0;
return {v, p.second};
}
auto p = split(lc[v], k);
lc[v] = p.second;
upd(v);
anc[v] = 0;
return {p.first, v};
}
int mrg(int a, int b) {
push(a);
push(b);
if (a == 0) {
upd(b);
return b;
}
if (b == 0) {
upd(a);
return a;
}
if (pr[a] > pr[b]) {
rc[a] = mrg(rc[a], b);
upd(a);
return a;
}
lc[b] = mrg(a, lc[b]);
upd(b);
return b;
}
int first_y_not_gr(int v, int k) {
if (v == 0)
return INF;
push(v);
push(lc[v]);
push(rc[v]);
if (lc[v] != 0 && mn_y[lc[v]] <= k)
return first_y_not_gr(lc[v], k);
if (val[v].second <= k)
return sz[lc[v]];
return first_y_not_gr(rc[v], k) + 1 + sz[lc[v]];
}
int last_x_not_gr(int v, int k) {
if (v == 0)
return -INF;
push(v);
push(lc[v]);
push(rc[v]);
if (rc[v] != 0 && mn_x[rc[v]] <= k)
return last_x_not_gr(rc[v], k) + sz[lc[v]] + 1;
if (val[v].first <= k)
return sz[lc[v]];
return last_x_not_gr(lc[v], k);
}
void asgn_x(int v, int l, int r, int x) {
push(v);
if (l > r)
return;
if (l == 0 && r == sz[v] - 1) {
up_x[v] = x;
push(v);
}
else {
asgn_x(lc[v], l, min(r, sz[lc[v]] - 1), x);
if (l <= sz[lc[v]] && r >= sz[lc[v]])
val[v].first = x;
asgn_x(rc[v], max(0, l - sz[lc[v]] - 1), r - sz[lc[v]] - 1, x);
upd(v);
}
}
void asgn_y(int v, int l, int r, int x) {
push(v);
if (l > r)
return;
if (l == 0 && r == sz[v] - 1) {
up_y[v] = x;
push(v);
}
else {
asgn_y(lc[v], l, min(r, sz[lc[v]] - 1), x);
if (l <= sz[lc[v]] && r >= sz[lc[v]])
val[v].second = x;
asgn_y(rc[v], max(0, l - sz[lc[v]] - 1), r - sz[lc[v]] - 1, x);
upd(v);
}
}
void prt(int v) {
if (v == 0)
return;
push(v);
prt(lc[v]);
cout << val[v].first << " " << val[v].second << "\n";
prt(rc[v]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, q;
cin >> n >> m >> q;
mt19937 rnd(time(0));
for (int i = 1; i < N; i++) {
pr[i] = rnd();
sz[i] = 1;
}
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
pts.emplace_back(x, y);
val[i + 1] = {x, y};
vx.push_back(x);
}
for (int i = 0; i < q; i++) {
int type, x, y;
cin >> type >> x;
if (type == 1) {
qrs.push_back({type, x - 1});
}
else if (type == 2 || type == 3) {
qrs.push_back({type, x});
}
else {
cin >> y;
qrs.push_back({type, (int)pts.size()});
pts.push_back({x, y});
vx.push_back(x);
val[pts.size()] = {x, y};
}
}
sort(all(vx));
vx.erase(unique(all(vx)), vx.end());
for (int i = 0; i < m; i++) {
add_pt(lower_bound(all(vx), pts[i].first) - vx.begin(), make_pair(pts[i].second, i));
}
int rt = 0;
for (const Q &q : qrs) {
if (q.t == 1) {
pair<int, int> ans = val[q.x + 1];;
int v = q.x + 1;
while (v != 0) {
if (up_x[v])
ans.first = up_x[v];
if (up_y[v])
ans.second = up_y[v];
v = anc[v];
}
cout << ans.first << " " << ans.second << "\n";
}
else if (q.t == 2) {
int l = first_y_not_gr(rt, q.x),
r = last_x_not_gr(rt, n - q.x);
// if (q.x == 2) {
// cout << l << " " << r << "\n";
// }
asgn_x(rt, l, r, n - q.x);
pts_to_add.clear();
int b = upper_bound(all(vx), n - q.x) - vx.begin();
b--;
get_pts_to_add(b, q.x);
for (int i : pts_to_add) {
i++;
val[i].first = n - q.x;
auto p = split(rt, val[i]);
rt = mrg(p.first, mrg(i, p.second));
}
}
else if (q.t == 3) {
int l = first_y_not_gr(rt, n - q.x),
r = last_x_not_gr(rt, q.x);
asgn_y(rt, l, r, n - q.x);
pts_to_add.clear();
int b = upper_bound(all(vx), q.x) - vx.begin();
b--;
get_pts_to_add(b, n - q.x);
for (int i : pts_to_add) {
i++;
val[i].second = n - q.x;
auto p = split(rt, val[i]);
rt = mrg(p.first, mrg(i, p.second));
}
}
else {
add_pt(lower_bound(all(vx), pts[q.x].first) - vx.begin(), make_pair(pts[q.x].second, q.x));
}
// prt(rt);
// cout << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |