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;
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] + 1, upds, ID);
}
if(T == 2) {
int L; upds++;
cin >> L;
mods.emplace_back('X', L);
}
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].first << '\n';
return;
}
/**
Istenem! Nu poate fi real.
-- Surse verificate
*/
Compilation message (stderr)
sweeping.cpp:24:4: error: expected ';' at end of member declaration
24 | ns updnode(ns node, ns x, int side) {
| ^~
| ;
sweeping.cpp:24:4: error: 'Treap<T>::pns Treap<T>::ns' conflicts with a previous declaration
sweeping.cpp:21:10: note: previous declaration 'using ns = struct Treap<T>::Node*'
21 | using ns = Node*;
| ^~
sweeping.cpp:24:7: error: ISO C++ forbids declaration of 'updnode' with no type [-fpermissive]
24 | ns updnode(ns node, ns x, int side) {
| ^~~~~~~
sweeping.cpp:55:12: error: 'nmax' was not declared in this scope; did you mean 'fmax'?
55 | pii points[nmax];
| ^~~~
| fmax
sweeping.cpp:56:19: error: 'nmax' was not declared in this scope; did you mean 'fmax'?
56 | vector<int> lefts[nmax * 2];
| ^~~~
| fmax
sweeping.cpp: In function 'void push(int, int, int, int, int, int)':
sweeping.cpp:66:29: error: 'lefts' was not declared in this scope
66 | if(l <= cl && cr <= r) { lefts[node].emplace_back(T); return; }
| ^~~~~
sweeping.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int mid = cl + cr >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
| ~~~^~~~
sweeping.cpp: In function 'void effectuate(int, int, int)':
sweeping.cpp:74:20: error: 'lefts' was not declared in this scope
74 | for(auto a : lefts[node]) {
| ^~~~~
sweeping.cpp:76:13: error: 'points' was not declared in this scope; did you mean 'printf'?
76 | points[a].first = max(points[a].first, (points[a].second <= mods[i].L? N - mods[i].L : points[a].first));
| ^~~~~~
| printf
sweeping.cpp:78:13: error: 'points' was not declared in this scope; did you mean 'printf'?
78 | points[a].second = max(points[a].second, (points[a].first <= mods[i].L? N - mods[i].L : points[a].second));
| ^~~~~~
| printf
sweeping.cpp: In function 'void walk(int, int, int)':
sweeping.cpp:84:28: error: expected ';' before 'if'
84 | effectuate(node, cl, cr)
| ^
| ;
85 | if(cl == cr) { return; }
| ~~
sweeping.cpp:86:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid = cl + cr >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
| ~~~^~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:107:10: error: 'points' was not declared in this scope; did you mean 'printf'?
107 | points[ID] = initstate[--start];
| ^~~~~~
| printf
sweeping.cpp:132:15: error: 'points' was not declared in this scope; did you mean 'printf'?
132 | cout << points[x].first << ' ' << points[x].first << '\n';
| ^~~~~~
| printf
sweeping.cpp:133:4: error: return-statement with no value, in function returning 'int' [-fpermissive]
133 | return;
| ^~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/string:41,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from sweeping.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = Update; _Args = {char, int&}; _Tp = Update]':
/usr/include/c++/10/bits/alloc_traits.h:512:17: required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = Update; _Args = {char, int&}; _Tp = Update; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<Update>]'
/usr/include/c++/10/bits/vector.tcc:115:30: required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {char, int&}; _Tp = Update; _Alloc = std::allocator<Update>; std::vector<_Tp, _Alloc>::reference = Update&]'
sweeping.cpp:113:34: required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'Update::Update(int&)'
sweeping.cpp:58:8: note: candidate: 'Update::Update()'
58 | struct Update {
| ^~~~~~
sweeping.cpp:58:8: note: candidate expects 0 arguments, 1 provided
sweeping.cpp:58:8: note: candidate: 'constexpr Update::Update(const Update&)'
sweeping.cpp:58:8: note: no known conversion for argument 1 from 'int' to 'const Update&'
sweeping.cpp:58:8: note: candidate: 'constexpr Update::Update(Update&&)'
sweeping.cpp:58:8: note: no known conversion for argument 1 from 'int' to 'Update&&'