/*input
8 1 8
1 5
4 4 1
2 6
1 2
2 3
4 2 2
2 5
1 1
1 3
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const int MAXN = 1500007, INF = 1e9 + 8;
int N, M, Q;
pair<int, int> ans[MAXN];
#define x first
#define y second
void minimize(int &x, int y) { x = (x < y ? x : y); }
void maximize(int &x, int y) { x = (x > y ? x : y); }
struct Event
{
int type, x, id;
} events[MAXN];
struct SegmentTree
{
int N;
vector<int> val, lazy;
void init(int _N, int x = -1)
{
N = _N;
val.assign(N << 2, x);
lazy.assign(N << 2, x);
}
void pushdown(int rt)
{
if (~lazy[rt]) {
maximize(val[rt << 1], lazy[rt]);
maximize(val[rt << 1 | 1], lazy[rt]);
maximize(lazy[rt << 1], lazy[rt]);
maximize(lazy[rt << 1 | 1], lazy[rt]);
lazy[rt] = -1;
}
}
void modify(int l, int r, int x, int rt, int lo, int hi)
{
if (hi < l || r < lo) return;
if (l <= lo && hi <= r) return maximize(val[rt], x), maximize(lazy[rt], x);
pushdown(rt);
int md = (lo + hi) >> 1;
modify(l, r, x, rt << 1, lo, md);
modify(l, r, x, rt << 1 | 1, md + 1, hi);
}
void modify(int l, int r, int x)
{
modify(l, r, x, 1, 0, N - 1);
}
int get(int i, int rt, int lo, int hi)
{
if (lo == hi) return val[rt];
pushdown(rt);
int md = (lo + hi) >> 1;
if (i <= md) return get(i, rt << 1, lo, md);
else return get(i, rt << 1 | 1, md + 1, hi);
}
int get(int i)
{
return get(i, 1, 0, N - 1);
}
} st_h, st_v;
struct DSU
{
int N = 0;
vector<int> dsu, lo, hi;
void init(int _N)
{
N = _N;
dsu.resize(N), lo.resize(N), hi.resize(N);
for (int i = 0; i < N; ++i) dsu[i] = -1, lo[i] = i, hi[i] = i + 1;
}
int root(int x) { return (dsu[x] < 0 ? x : dsu[x] = root(dsu[x])); }
void join(int x, int y)
{
x = root(x), y = root(y);
if (x == y) return;
if (dsu[x] > dsu[y]) swap(x, y);
dsu[x] += dsu[y];
dsu[y] = x;
minimize(lo[x], lo[y]);
maximize(hi[x], hi[y]);
}
pair<int, int> get(int id) { return id = root(id), make_pair(lo[id], hi[id]); }
} dsu;
pair<int, int> cur_pos[MAXN];
vector<int> pos_x, rem, seg_h, seg_v, dusts, group;
vector<pair<int, int>> tmp_pos;
vector<vector<int>> segs_h;
void solve(int lo, int hi)
{
if (lo == hi) return;
int mid = (lo + hi) >> 1;
solve(lo, mid), solve(mid + 1, hi);
// identify dust IDs
int from_id = INF, to_id = 0;
for (int i = lo; i <= mid; ++i) {
if (events[i].type == 4) {
minimize(from_id, events[i].id);
maximize(to_id, events[i].id);
}
}
if (from_id > to_id) return;
// cout << "\nrange " << lo << ' ' << hi << endl;
// identify pos_x
pos_x.clear(), pos_x.push_back(-1);
for (int i = mid + 1; i <= hi; ++i) {
if (events[i].type == 2 || events[i].type == 3) {
pos_x.push_back(events[i].x);
}
}
sort(pos_x.begin(), pos_x.end()), pos_x.erase(unique(pos_x.begin(), pos_x.end()), pos_x.end());
auto get_x = [&](int x) -> int { return int(lower_bound(pos_x.begin(), pos_x.end(), x) - pos_x.begin()); };
int X = (int) pos_x.size();
pos_x.push_back(N);
// cout << "pos_x "; for (int x : pos_x) cout << x << ' '; cout << endl;
// find segments
rem.assign(hi - mid, -1);
seg_h.assign(X + 1, -1), seg_v.assign(X + 1, -1);
st_h.init(X, -1), st_v.init(X, -1);
segs_h.assign(X + 1, vector<int>(0));
for (int i = mid + 1; i <= hi; ++i) {
if (events[i].type == 2) {
int x = get_x(events[i].x);
int p = get_x(st_h.get(x));
if (p == x) continue;
assert(p < x);
if (!~seg_h[x]) {
rem[i - (mid + 1)] = x;
seg_h[x] = p;
segs_h[p + 1].push_back(x);
st_v.modify(p + 1, x, N - events[i].x);
}
} else if (events[i].type == 3) {
int x = get_x(events[i].x);
int p = get_x(N - st_v.get(x));
if (p == x) continue;
assert(p > x);
if (!~seg_v[x]) {
rem[i - (mid + 1)] = x;
seg_v[x] = p;
st_h.modify(x, p - 1, events[i].x);
}
}
}
// find dusts
dusts.resize(to_id - from_id + 1);
iota(dusts.begin(), dusts.end(), from_id);
sort(dusts.begin(), dusts.end(), [&](int i, int j) { return cur_pos[i].x < cur_pos[j].x; });
// sort dusts into dsu groups
group.assign(to_id - from_id + 1, -1);
st_v.init(X + 1, 0);
dsu.init(X);
vector<int>::iterator dust_it = dusts.begin();
for (int x = 0; x <= X; ++x) {
for (int x1 : segs_h[x]) {
// cout << "horizontal " << x1 << endl;
st_v.modify(x1 + 1, X, x1);
}
for (; dust_it != dusts.end() && cur_pos[*dust_it].x <= pos_x[x]; ++dust_it) {
int id = *dust_it;
group[id - from_id] = st_v.get(get_x(N - cur_pos[id].y));
// cout << "group " << id << ": " << group[id - from_id] << " | " << N - cur_pos[id].y << endl;
}
if (~seg_v[x]) {
// cout << "vertical " << x << ": " << seg_v[x] << endl;
st_v.modify(x + 1, seg_v[x], x);
}
}
assert(dust_it == dusts.end());
// calc final pos
auto get_pos = [&](pair<int, int> pnt, int g) -> pair<int, int> {
pair<int, int> lim = dsu.get(g);
maximize(pnt.first, pos_x[lim.first] + 1);
minimize(pnt.first, pos_x[lim.second]);
maximize(pnt.second, N - pos_x[lim.second]);
minimize(pnt.second, N - pos_x[lim.first] - 1);
return pnt;
};
tmp_pos.resize(to_id - from_id + 1);
for (int i = from_id; i <= to_id; ++i) {
tmp_pos[i - from_id] = cur_pos[i];
// cout << cur_pos[i].x << ' ' << cur_pos[i].y << " -> ";
cur_pos[i] = get_pos(tmp_pos[i - from_id], group[i - from_id]);
// cout << cur_pos[i].x << ' ' << cur_pos[i].y;
// auto x = dsu.get(group[i - from_id]); cout << " = " << pos_x[x.x] << ' ' << pos_x[x.y] << endl;
}
for (int i = hi; i >= mid + 1; --i) {
if (events[i].type == 1 && events[i].x >= from_id && events[i].x <= to_id) {
int dust_id = events[i].x;
// cout << "ans " << events[i].id << ": " << dust_id << " _ " << tmp_pos[dust_id - from_id].x << ' ' << tmp_pos[dust_id - from_id].y << " -> ";
cout << flush;
ans[events[i].id] = get_pos(tmp_pos[dust_id - from_id], group[dust_id - from_id]);
// cout << ans[events[i].id].x << ' ' << ans[events[i].id].y;
// auto x = dsu.get(group[dust_id - from_id]); cout << " = " << pos_x[x.x] << ' ' << pos_x[x.y] << endl;
} else if (~rem[i - (mid + 1)]) {
int x = rem[i - (mid + 1)];
// cout << "rem " << i << ": " << x << endl;
dsu.join(x - 1, x);
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> Q;
int num_events = 0, num_dusts = 0, num_questions = 0;
for (int i = 0; i < M; ++i) {
auto &cur = events[++num_events];
cur.type = 4;
cur.id = ++num_dusts;
cin >> cur_pos[cur.id].first >> cur_pos[cur.id].second;
}
for (int i = 0; i < Q; ++i) {
auto &cur = events[++num_events];
cin >> cur.type;
if (cur.type == 1) {
cin >> cur.x;
cur.id = ++num_questions;
} else if (cur.type == 2) {
cin >> cur.x;
cur.x = N - cur.x - 1;
} else if (cur.type == 3) {
cin >> cur.x;
} else {
cur.id = ++num_dusts;
cin >> cur_pos[cur.id].first >> cur_pos[cur.id].second;
}
}
solve(1, num_events);
for (int i = 1; i <= num_questions; ++i) {
cout << ans[i].first << ' ' << ans[i].second << '\n';
}
}
Compilation message
sweeping.cpp: In function 'void solve(int, int)':
sweeping.cpp:181:2: error: 'iota' was not declared in this scope
iota(dusts.begin(), dusts.end(), from_id);
^~~~
sweeping.cpp:181:2: note: suggested alternative: 'int'
iota(dusts.begin(), dusts.end(), from_id);
^~~~
int
