#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
mt19937 true_rng(chrono::steady_clock::now().time_since_epoch().count());
struct rrandom {
int a = true_rng() & 1, b = true_rng() & 1;
int x;
rrandom(int t) { x = t; }
int operator()() { x = a * x + b; return x; }
};
#ifndef DLOCAL
rrandom rng(chrono::steady_clock::now().time_since_epoch().count());
#else
rrandom rng(69420);
#endif
template<typename T>
struct Treap { // neironic de 2 ani nu am mai bagat treap. Gen, doi ani, se implinesc 3 in 3 luni. E jale
struct Node {
T data;
Node *l, *r;
} *nil = new Node{T(), 0, 0};
using ns = Node*;
struct pns { ns l; ns r; };
ns updnode(ns node, ns x, int side) {
(side? node -> r : node -> l) = x;
node -> data.pull(node -> l -> data, node -> r -> data);
return node;
}
void push(ns node) {
if(node == nil) return;
node -> data.push(node -> l -> data, node -> r -> data);
return;
}
ns merge(ns l, ns r) {
push(l), push(r);
return l == nil? r :
r == nil? l :
rng() % 2 == 0? updnode(l, merge(l -> r, r), 1):
updnode(r, merge(l, r -> l), 0);
}
template<class CB> pns split(CB&& cb, ns node) { // 1 daca dreapta, 0 daca stanga
push(node);
pns tmp;
return node == nil? pns{nil, nil}:
!cb(node)? (tmp = split(cb, node -> l), tmp.r = updnode(node, tmp.r, 0), tmp):
(tmp = split(cb, node -> r), tmp.l = updnode(node, tmp.l, 1), tmp);
}
template<class CB> pns split(CB&& cb) { return split(cb, root); }
template<class CB> void walkAll(CB&& cb, ns node) {
if(node == nil) return;
push(node);
cb(node);
walkAll(cb, node -> l); walkAll(cb, node -> r);
}
ns root = nil;
};
int N;
const int nmax = 1e6 + 5;
pii points[nmax];
vector<int> lefts[nmax * 2];
struct Update {
char type; // modifica X sau Y
int L;
};
vector<Update> mods;
void push(int l, int r, int T, int node = 1, int cl = 0, int cr = sz(mods) - 1) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r) { lefts[node].emplace_back(T); return; }
int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
push(l, r, T, L, cl, mid);
push(l, r, T, R, mid + 1, cr);
}
struct Segment {
int l, r, rmax;
int ID;
void pull(const Segment& L, const Segment& R) { rmax = max({r, L.rmax, R.rmax}); }
void push(const Segment& L, const Segment& R) {;}
};
struct ZeroZero : private Treap<Segment> {
void insert(int x, int y, int ID) {
int l = x, r = N - y;
auto [L, R] = split([&](ns node) { return node -> data.l <= l; }, root);
L = merge(L, new Node{Segment{l, r, r, ID}, nil, nil});
root = merge(L, R);
}
vector<int> extract(int P) {
auto [focus, outside] = split([&](ns node) { return node -> data.l <= P; }, root);
vector<int> ids;
while(focus != nil && focus -> data.rmax >= P) {
auto [mid, R] = split([&](ns node){ return max(node -> l -> data.rmax, node -> data.r) < P; }, focus);
auto [single, rest] = split([&, found = 0](ns node) mutable {
if(!found) { return (node -> l == nil? (found = 1, 1) : 0); }
return 0;
}, R);
ids.emplace_back(single -> data.ID);
focus = merge(mid, rest);
}
root = merge(focus, outside);
return ids;
}
};
struct Point {
int x, y;
int lazyx, lazyy;
int ID;
void pull(const Point& L, const Point& R) {;}
void applyX(int lazyx_) { x = max(x, lazyx_); lazyx = max(lazyx_, lazyx); }
void applyY(int lazyy_) { y = max(y, lazyy_); lazyy = max(lazyy_, lazyy); }
void push(Point& L, Point& R) {
L.applyX(lazyx);
R.applyX(lazyx);
lazyx = 0;
L.applyY(lazyy);
R.applyY(lazyy);
lazyy = 0;
}
};
struct Scarita : Treap<Point> {
void insert(int x, int y, int ID) {
auto [L, R] = split([&](ns node) { return pii{node -> data.x, -node -> data.y} < pii{x, -y}; }, root);
root = merge(merge(L, new Node{Point{x, y, 0, 0, ID}, nil, nil}), R);
}
tuple<ns, ns, ns> splitRect(int P) {
auto [L, mid] = split([&](ns node) { return node -> data.y > N - P; }, root);
auto [want, R] = split([&](ns node) { return node -> data.x <= P; }, mid);
return tuple<ns, ns, ns>{L, want, R};
}
vector<int> extract(int P) {
vector<int> ids;
auto [L, mid, R] = splitRect(P);
walkAll([&](ns node) { points[node -> data.ID] = pii{node -> data.x, node -> data.y}; ids.emplace_back(node -> data.ID); }, mid);
root = merge(L, R);
return ids;
}
void maxY(int P) {
auto [L, mid, R] = splitRect(P);
mid -> data.applyY(N - P);
root = merge(L, merge(mid, R));
}
void maxX(int P) {
auto [L, mid, R] = splitRect(P);
mid -> data.applyX(P);
root = merge(merge(L, mid), R);
}
};
void effectuate(int NODE, int cl, int cr) {
ZeroZero zerozero;
for(auto x : lefts[NODE]) zerozero.insert(points[x].first, points[x].second, x);
Scarita doarX, doarY, ambele;
for(int i = cl; i <= cr; i++) {
{ // evolutia lui doarY
if(mods[i].type == 'Y') doarY.maxY(mods[i].L);
else {
auto schimb = doarY.extract(mods[i].L);
for(auto x : schimb) ambele.insert(points[x].first, points[x].second, x);
}
}
{ // evolutia lui doarX
if(mods[i].type == 'X') doarX.maxX(mods[i].L);
else {
auto schimb = doarX.extract(mods[i].L);
for(auto x : schimb) ambele.insert(points[x].first, points[x].second, x);
}
}
{ // evolutia lui zero zero
auto schimb = zerozero.extract(mods[i].L);
for(auto x : schimb) {
auto &[a, b] = points[x];
if(mods[i].type == 'X') a = max(a, (b <= N - mods[i].L? mods[i].L : a)), doarX.insert(a, b, x);
else b = max(b, (a <= mods[i].L? N - mods[i].L : b)), doarY.insert(a, b, x);
}
}
{ // evolutia lui ambele
if(mods[i].type == 'Y') ambele.maxY(mods[i].L);
else ambele.maxX(mods[i].L);
}
}
doarX.walkAll([&](auto node) {
points[node -> data.ID] = pii{node -> data.x, node -> data.y};
}, doarX.root);
doarY.walkAll([&](auto node) {
points[node -> data.ID] = pii{node -> data.x, node -> data.y};
}, doarY.root);
ambele.walkAll([&](auto node) {
points[node -> data.ID] = pii{node -> data.x, node -> data.y};
}, ambele.root);
return;
}
void walk(int node = 1, int cl = 0, int cr = sz(mods) - 1) {
effectuate(node, cl, cr);
if(cl >= cr) return;
int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
walk(L, cl, mid);
walk(R, mid + 1, cr);
return;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int m, q;
cin >> N >> m >> q;
vector<pii> initstate(m);
vector<int> spoz(m, 0), querylinks;
for(auto &[a, b] : initstate) { cin >> a >> b; }
vector<tii> pushes;
for(int i = 0, T, upds = 0; i < q; i++) {
cin >> T;
if(T == 1) {
int start, ID = sz(querylinks);
cin >> start;
points[ID] = initstate[--start];
pushes.emplace_back(spoz[start], upds - 1, ID);
querylinks.emplace_back(ID);
}
else if(T == 2) {
int L; upds++;
cin >> L;
mods.emplace_back(Update{'X', N - L});
}
else if(T == 3) {
int L; upds++;
cin >> L;
mods.emplace_back(Update{'Y', L});
}
else {
int a, b;
cin >> a >> b;
initstate.emplace_back(a, b);
spoz.emplace_back(upds);
}
}
for(auto [l, r, T] : pushes) push(l, r, T);
walk();
for(auto x : querylinks)
cout << points[x].first << ' ' << points[x].second << '\n';
return 0;
}
/**
Istenem! Nu poate fi real.
-- Surse verificate
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
49500 KB |
Output is correct |
| 2 |
Correct |
22 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
9 ms |
47960 KB |
Output is correct |
| 4 |
Correct |
32 ms |
49428 KB |
Output is correct |
| 5 |
Correct |
11 ms |
48984 KB |
Output is correct |
| 6 |
Correct |
99 ms |
50260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10661 ms |
531528 KB |
Output is correct |
| 2 |
Execution timed out |
18040 ms |
107108 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18036 ms |
101000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18036 ms |
101000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
49500 KB |
Output is correct |
| 2 |
Correct |
22 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
9 ms |
47960 KB |
Output is correct |
| 4 |
Correct |
32 ms |
49428 KB |
Output is correct |
| 5 |
Correct |
11 ms |
48984 KB |
Output is correct |
| 6 |
Correct |
99 ms |
50260 KB |
Output is correct |
| 7 |
Correct |
10661 ms |
531528 KB |
Output is correct |
| 8 |
Execution timed out |
18040 ms |
107108 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
