| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1309777 | vlomaczk | The Collection Game (BOI21_swaps) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll inf = 1e18;
struct SegmentTreeBeats {
ll base;
vector<ll> L,mn,smn;
SegmentTreeBeats(ll n) {
ll lvl = ceil(log2(double(n)));
base = 1<<lvl;
L.assign(2*base,0);
mn.assign(2*base,0);
smn.assign(2*base,inf);
for(int i=1; i<base; ++i) smn[i] = 0;
}
void push(ll v, ll l, ll r) {
if(L[v]==0 || r>=2*base) return;
L[l] += L[v];
L[r] += L[v];
mn[l] += L[v];
if(smn[l] < inf) smn[l] += L[v];
mn[r] += L[v];
if(smn[r] < inf) smn[r] += L[v];
L[v] = 0;
}
void pull(ll v, ll l, ll r) {
mn[v] = min(mn[l], mn[r]);
smn[v] = inf;
if (mn[l] != mn[v]) smn[v] = min(smn[v], mn[l]);
if (mn[r] != mn[v]) smn[v] = min(smn[v], mn[r]);
smn[v] = min({smn[v], smn[l], smn[r]});
}
void update(ll v, ll a, ll b, ll p, ll k, ll val) {
if(b < p || k < a) return;
if(p <= a && b <= k) {
L[v] += val;
mn[v] += val;
if(smn[v] < inf) smn[v] += val;
return;
}
ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
push(v,l,r);
update(l,a,mid,p,k,val);
update(r,mid+1,b,p,k,val);
pull(v,l,r);
}
void max_with(ll v, ll a, ll b, ll x) {
if(mn[v] >= x) return;
if(smn[v] > x) {
mn[v] = x;
return;
}
ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
push(v,l,r);
max_with(l,a,mid,x);
max_with(r,mid+1,b,x);
pull(v,l,r);
}
ll Q(ll v, ll a, ll b, ll x) {
if(x < a || x > b) return inf;
if(a==b && a==x) return mn[v];
ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
push(v,l,r);
return min(Q(l,a,mid,x), Q(r,mid+1,b,x));
}
void add(ll l, ll r, ll val) { // Add val to [l,r]
update(1,0,base-1,l,r,val);
}
void max_with_zero() { //Foreach i : a[i] = max(a[i], 0)
max_with(1,0,base-1,0);
}
ll query(ll pos) { // Find value of a[pos]
return Q(1,0,base-1,pos);
}
};
struct Block {
ll type,amount,time;
};
struct SegTree {
ll base;
vector<ll> T, L;
SegTree(ll n) {
ll lvl = __lg(n) + 1;
base = 1<<lvl;
T.assign(2*base, 0);
L.assign(2*base, 0);
}
void push(ll v, ll l, ll r) {
if(L[v]==0 || r>=2*base) return;
T[l] += L[v];
T[r] += L[v];
L[l] += L[v];
L[r] += L[v];
L[v] = 0;
}
void update(ll v, ll a, ll b, ll l, ll r, ll val) {
if(b < l || r < a) return;
if(l<=a && b<=r) {
T[v] += val;
L[v] += val;
return;
}
ll lewy = 2*v; ll prawy = 2*v+1; ll mid=(a+b)/2;
push(v, lewy, prawy);
update(lewy,a,mid,l,r,val);
update(prawy,mid+1,b,l,r,val);
T[v] = max(T[lewy], T[prawy]);
}
ll find(ll v, ll a, ll b, ll x) {
if(a==b) return v - base;
ll lewy = 2*v; ll prawy = 2*v+1; ll mid=(a+b)/2;
push(v, lewy, prawy);
if(T[lewy] >= x) return find(lewy,a,mid,x);
return find(prawy,mid+1,b,x);
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n,m,q;
cin >> n >> m >> q;
vector<ll> ans;
vector<vector<pair<ll, ll>>> query(n+1);
vector<vector<Block>> bloki_add(n+1), bloki_del(n+2);
SegmentTreeBeats stb(n), stb2(n);
for(ll t=0; t<q; ++t) {
ll T; cin >> T;
if(T==1) {
ll l,r,c,k;
cin >> l >> r >> c >> k;
--l; --r;
bloki_add[l].push_back({c,k,t});
bloki_del[r+1].push_back({c,k,t});
stb.add(l,r,k);
stb2.add(l,r,k);
} else if(T==2) {
ll l,r,k;
cin >> l >> r >> k;
--l; --r;
stb.add(l,r,-k);
} else {
ll a,b;
cin >> a >> b;
--a;
ans.push_back(-1);
if(stb.query(a) < b) ans.back() = 0;
else query[a].push_back({b + stb2.query(a) - stb.query(a), ans.size()-1});
}
stb.max_with_zero();
}
SegTree st(2*q+1);
vector<ll> typ(2*q+1);
for(ll i=0; i<n; ++i) {
for(auto[c,k,t] : bloki_add[i]) {
typ[t] = c;
st.update(1,0,st.base-1,t,st.base-1,k);
}
for(auto[c,k,t] : bloki_del[i]) {
typ[t] = -1;
st.update(1,0,st.base-1,t,st.base-1,-k);
}
for(auto[poz, idx] : query[i]) ans[idx] = typ[st.find(1,0,st.base-1,poz)];
}
for(auto x : ans) cout << x << '\n';
return 0;
}