| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 996822 | cadmiumsky | Sweeping (JOI20_sweeping) | C++17 | 0 ms | 0 KiB |
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>
#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 = 5e5 + 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('X', L);
}
else if(T == 3) {
int L; upds++;
cin >> L;
mods.emplace_back('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
*/