Submission #996921

#TimeUsernameProblemLanguageResultExecution timeMemory
996921cadmiumskySweeping (JOI20_sweeping)C++17
100 / 100
6025 ms687008 KiB
#pragma GCC optimize("Ofast,fast-math,unroll-loops") #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>; #ifndef DLOCAL mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #else mt19937 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; int pri; } *nil = new Node{T(), 0, 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 : l -> pri > r -> pri? 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, (int)rng()}); 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, (int)rng()}), 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...