Submission #996824

#TimeUsernameProblemLanguageResultExecution timeMemory
996824cadmiumskySweeping (JOI20_sweeping)C++17
0 / 100
1264 ms2097152 KiB
#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>; 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) { 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); } }; int N; const int nmax = 5e3 + 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); } void effectuate(int node, int cl, int cr) { for(int i = cl; i <= cr; i++) { for(auto a : lefts[node]) { if(mods[i].type == 'X') points[a].first = max(points[a].first, (points[a].second <= mods[i].L? N - mods[i].L : points[a].first)); else points[a].second = max(points[a].second, (points[a].first <= mods[i].L? N - mods[i].L : points[a].second)); } } } 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', 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...