| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1077439 | awu | Food Court (JOI21_foodcourt) | C++14 | 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/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [](decltype(x) _x) {cerr << #x << " = " << _x << endl; return _x;}(x)
using pii = pair<int, int>;
// const int inf = 1ll << 60;
const int inf = 1 << 30;
template <class T, class _ = decltype(begin(declval<T>()))>
enable_if_t<!is_same_v<T, string>, ostream&> operator<<(ostream& out, T a) {
string dlm = "";
out << "{";
for(auto i : a) {
out << dlm << i;
dlm = ", ";
}
return out << "}";
}
struct segtree {
vector<int> t;
vector<pii> lz;
segtree(int s) {
int n = 1;
while(n < s) n *= 2;
t.resize(n * 2);
lz.resize(n * 2);
}
void apply(int n, pii upd) {
lz[n].s += upd.f;
if(lz[n].s < 0) {
lz[n].f += lz[n].s;
lz[n].s = upd.s;
} else {
lz[n].s += upd.s;
}
}
void push(int n) {
t[n] += lz[n].f;
t[n] = max(t[n], 0ll);
t[n] += lz[n].s;
if(n < t.size() / 2) {
apply(n * 2, lz[n]);
apply(n * 2 + 1, lz[n]);
}
lz[n] = {0, 0};
}
void update(int ul, int ur, int v, int n = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = t.size() / 2;
if(ul >= tr || ur <= tl) return;
if(ul <= tl && ur >= tr) {
apply(n, {v, 0});
return;
}
push(n);
int tm = (tl + tr) / 2;
update(ul, ur, v, n * 2, tl, tm);
update(ul, ur, v, n * 2 + 1, tm, tr);
push(n * 2);
push(n * 2 + 1);
t[n] = min(t[n * 2], t[n * 2 + 1]);
}
int query(int i, int n = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = t.size() / 2;
push(n);
if(tl + 1 == tr) return t[n];
int tm = (tl + tr) / 2;
if(i < tm) return query(i, n * 2, tl, tm);
return query(i, n * 2 + 1, tm, tr);
}
};
struct segnode {
int v;
signed lc, rc;
void init();
void update(int, int, int, int);
int query(int, int, int, int);
};
const int MAX_Q = 250005;
segnode seg[MAX_Q * 300];
int segsize = 1;
void segnode::init() {
if(!lc) {
lc = segsize;
segsize++;
}
if(!rc) {
rc = segsize;
segsize++;
}
}
void segnode::update(int i, int x, int tl, int tr) {
if(tl + 1 == tr) {
v = x;
return;
}
signed tm = (tl + tr) / 2;
if(i < tm) {
if(!lc) {
lc = segsize;
segsize++;
}
seg[lc].update(i, x, tl, tm);
v = seg[lc].v;
if(rc) v += seg[rc].v;
} else {
if(!rc) {
rc = segsize;
segsize++;
}
seg[rc].update(i, x, tm, tr);
v = seg[rc].v;
if(lc) v += seg[lc].v;
}
}
int segnode::query(int ql, int qr, int tl, int tr) {
if(ql >= tr || qr <= tl) return 0;
if(ql <= tl && qr >= tr) return v;
if(v == 0) return 0;
int tm = (tl + tr) / 2;
return (lc ? seg[lc].query(ql, qr, tl, tm) : 0) + (rc ? seg[rc].query(ql, qr, tm, tr) : 0);
}
struct segtree2 {
int n = 1;
segtree2(int s) {
while(n < s) n *= 2;
segsize = n * 2;
}
void update(int l, int r, int v, int time) {
for(l += n, r += n; l < r; l /= 2, r /= 2) {
if(l & 1) seg[l++].update(time, v, 0, MAX_Q);
if(r & 1) seg[--r].update(time, v, 0, MAX_Q);
}
}
int query(int i, int x) { // query earliest time suffix sum of people exceeds x (inclusive)
vector<signed> nodes;
for(i += n; i; i /= 2) {
nodes.push_back(i);
}
int tl = 0, tr = MAX_Q;
while(true) {
if(tl + 1 == tr) return tl;
int acc = 0;
for(auto node : nodes) {
if(seg[node].rc) acc += seg[seg[node].rc].v;
}
vector<signed> newnodes;
if(acc >= x) {
for(auto node : nodes) {
if(seg[node].rc) newnodes.push_back(seg[node].rc);
}
tl = (tl + tr) / 2;
} else {
x -= acc;
for(auto node : nodes) {
if(seg[node].lc) newnodes.push_back(seg[node].lc);
}
tr = (tl + tr) / 2;
}
swap(nodes, newnodes);
}
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q; cin >> n >> m >> q;
segtree st(n);
segtree2 st2(n);
vector<int> id(q, -1); // look up c given update time
for(int i = 0; i < q; i++) {
int t; cin >> t;
if(t == 1) {
int l, r, c, k; cin >> l >> r >> c >> k; l--;
st.update(l, r, k);
st2.update(l, r, k, i);
id[i] = c;
} else if(t == 2) {
int l, r, k; cin >> l >> r >> k; l--;
st.update(l, r, -k);
} else {
int a, b; cin >> a >> b; a--; b--;
int x = st.query(a);
if(b >= x) cout << 0 << endl;
else {
int ri = x - b;
int lo = st2.query(a, ri);
cout << id[lo] << "\n" ;
}
}
}
}