#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 5e5 + 5;
struct SumSeg {
vl lz;
vl st;
int sz;
void init(int n) {
sz = 1;
while (sz < n) sz <<= 1;
lz.assign(2 * sz, 0);
st.assign(2 * sz, 0);
}
void pull(int i) {
st[i] = st[2 * i] + st[2 * i + 1];
}
void push(int i, int l, int r) {
st[i] += (r - l + 1) * lz[i];
if (l != r) {
lz[2 * i] += lz[i];
lz[2 * i + 1] += lz[i];
}
lz[i] = 0;
}
void upd(int lo, int hi, ll inc, int i = 1, int l = 0, int r = -1) {
if (r == -1) r += sz;
push(i, l, r);
if (hi < l || r < lo) return;
if (lo <= l && r <= hi) {
lz[i] = inc;
push(i, l, r);
return;
}
int m = (l + r) >> 1;
upd(lo, hi, inc, 2 * i, l, m);
upd(lo, hi, inc, 2 * i + 1, m + 1, r);
pull(i);
}
ll query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
if (r == -1) r += sz;
push(i, l, r);
if (hi < l || r < lo) return 0;
if (lo <= l && r <= hi) return st[i];
int m = (l + r) >> 1;
return query(lo, hi, 2 * i, l, m) + query(lo, hi, 2 * i + 1, m + 1, r);
}
};
template <class C> struct SegmentTreeBeats {
using T = std::pair<std::pair<C, C>, int>;
const C INF = std::numeric_limits<C>::max();
std::vector<C> mx_mod, mn_mod, mod, sum;
std::vector<T> mx, mn;
int sz;
void init(int sz_) {
sz = 1;
while (sz < sz_) sz *= 2;
mx_mod.assign(2 * sz, 0);
mn_mod.assign(2 * sz, 0);
mod.assign(2 * sz, 0);
sum.assign(2 * sz, 0);
mx.assign(2 * sz, {{0, 0}, 0});
mn.assign(2 * sz, {{0, 0}, 0});
build();
}
void build(int ind = 1, int L = 0, int R = -1) {
if (R == -1) R += sz;
mx_mod[ind] = INF, mn_mod[ind] = -INF, mod[ind] = 0;
if (L == R) {
mx[ind] = {{0, -INF}, 1};
mn[ind] = {{0, INF}, 1};
sum[ind] = 0;
return;
}
int M = (L + R) / 2;
build(2 * ind, L, M); build(2 * ind + 1, M + 1, R);
pull(ind);
}
T comb_mn(T a, T b) {
if (a > b)
std::swap(a, b);
if (a.first.first == b.first.first)
return {{a.first.first,
std::min(a.first.second, b.first.second)},
a.second + b.second};
return {{a.first.first, std::min(a.first.second, b.first.first)}, a.second};
}
T comb_mx(T a, T b) {
if (a < b) std::swap(a, b);
if (a.first.first == b.first.first)
return {{a.first.first,
std::max(a.first.second, b.first.second)},
a.second + b.second};
return {{a.first.first, std::max(a.first.second, b.first.first)},
a.second};
}
void pull(int ind) {
sum[ind] = sum[2 * ind] + sum[2 * ind + 1];
mn[ind] = comb_mn(mn[2 * ind], mn[2 * ind + 1]);
mx[ind] = comb_mx(mx[2 * ind], mx[2 * ind + 1]);
}
void push(int ind, int L, int R) {
auto chk = [](C& a, C b, C c) {
if (a == b)
a = c;
};
if (mn_mod[ind] != -INF) {
if (mn_mod[ind] > mn[ind].first.first) {
sum[ind] += (mn_mod[ind] - mn[ind].first.first) * mn[ind].second;
chk(mx[ind].first.first, mn[ind].first.first, mn_mod[ind]);
chk(mx[ind].first.second, mn[ind].first.first, mn_mod[ind]);
mn[ind].first.first = mn_mod[ind];
if (L != R) {
for (int i = 0; i < 2; i++) {
int pos = 2 * ind + i;
mn_mod[pos] = std::max(mn_mod[pos], mn_mod[ind] - mod[pos]);
mx_mod[pos] = std::max(mx_mod[pos], mn_mod[pos]);
}
}
}
mn_mod[ind] = -INF;
}
if (mx_mod[ind] != INF) {
if (mx_mod[ind] < mx[ind].first.first) {
sum[ind] += (mx_mod[ind] - mx[ind].first.first) * mx[ind].second;
chk(mn[ind].first.first, mx[ind].first.first, mx_mod[ind]);
chk(mn[ind].first.second, mx[ind].first.first, mx_mod[ind]);
mx[ind].first.first = mx_mod[ind];
if (L != R) {
for (int i = 0; i < 2; i++) {
int pos = 2 * ind + i;
mx_mod[pos] = std::min(mx_mod[pos], mx_mod[ind] - mod[pos]);
mn_mod[pos] = std::min(mn_mod[pos], mx_mod[pos]);
}
}
}
mx_mod[ind] = INF;
}
if (mod[ind] != 0) {
sum[ind] += mod[ind] * (R - L + 1);
auto inc = [&](T& a, C b) {
if (std::abs(a.first.first) != INF)
a.first.first += b;
if (std::abs(a.first.second) != INF)
a.first.second += b;
};
inc(mx[ind], mod[ind]); inc(mn[ind], mod[ind]);
if (L != R) {
for (int i = 0; i < 2; i++) {
int pos = 2 * ind + i;
mod[pos] += mod[ind];
}
}
mod[ind] = 0;
}
}
C qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R += sz;
push(ind, L, R);
if (R < lo || hi < L)
return 0;
if (lo <= L && R <= hi)
return sum[ind];
int M = (L + R) / 2;
return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
}
C qmax(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R += sz;
push(ind, L, R);
if (R < lo || hi < L)
return -INF;
if (lo <= L && R <= hi)
return mx[ind].first.first;
int M = (L + R) / 2;
return std::max(qmax(lo, hi, 2 * ind, L, M), qmax(lo, hi, 2 * ind + 1, M + 1, R));
}
C qmin(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R += sz;
push(ind, L, R);
if (R < lo || hi < L)
return INF;
if (lo <= L && R <= hi)
return mn[ind].first.first;
int M = (L + R) / 2;
return std::min(qmin(lo, hi, 2 * ind, L, M), qmin(lo, hi, 2 * ind + 1, M + 1, R));
}
void upd(int t, int lo, int hi, C b, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R += sz;
push(ind, L, R);
if (R < lo || hi < L)
return;
if (t == 0)
if (b >= mx[ind].first.first)
return;
else if (t == 1)
if (b <= mn[ind].first.first)
return;
if (lo <= L && R <= hi) {
if (t == 0) {
if (b > mx[ind].first.second) {
mx_mod[ind] = b;
push(ind, L, R);
return;
}
} else if (t == 1) {
if (b < mn[ind].first.second) {
mn_mod[ind] = b;
push(ind, L, R);
return;
}
} else if (t == 2) {
mod[ind] = b;
push(ind, L, R);
return;
} else assert(false);
}
assert(L != R);
int M = (L + R) / 2;
upd(t, lo, hi, b, 2 * ind, L, M); upd(t, lo, hi, b, 2 * ind + 1, M + 1, R);
pull(ind);
}
};
const ll INF = 1e18;
struct MaxSeg {
vl lz;
vector<pair<ll, int>> st;
int sz;
void pull(int i) {
st[i] = max(st[2 * i], st[2 * i + 1]);
}
void init(int n) {
sz = 1;
while (sz < n) sz <<= 1;
lz.assign(2 * sz, 0);
st.resize(2 * sz);
f0r(i, sz) st[i + sz] = mp(0, i);
for (int i = sz - 1; i >= 1; i--) pull(i);
}
void push(int i, int l, int r) {
st[i].f += lz[i];
if (l != r) {
lz[2 * i] += lz[i];
lz[2 * i + 1] += lz[i];
}
lz[i] = 0;
}
void upd(int lo, int hi, ll inc, int i = 1, int l = 0, int r = -1) {
if (r == -1) r += sz;
push(i, l, r);
if (hi < l || r < lo) return;
if (lo <= l && r <= hi) {
lz[i] = inc;
push(i, l, r);
return;
}
int m = (l + r) >> 1;
upd(lo, hi, inc, 2 * i, l, m);
upd(lo, hi, inc, 2 * i + 1, m + 1, r);
pull(i);
}
pair<ll, int> query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
if (r == -1) r += sz;
push(i, l, r);
if (hi < l || r < lo) return mp(-2 * INF, -1);
if (lo <= l && r <= hi) return st[i];
int m = (l + r) >> 1;
return max(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r));
}
};
const int MAXN = 2.5e5 + 5;
struct Beats {
int n;
void init(int _n){ n=_n; }
struct info {
ll lzy_ad=0, lzy_mx=-INF, lzy_ad2=0;
} t[4*MAXN];
void push(int v, int tl, int tr){
if (tl == tr) return;
t[2*v].lzy_ad += t[v].lzy_ad;
t[2*v+1].lzy_ad += t[v].lzy_ad;
t[2*v].lzy_mx += t[v].lzy_ad;
t[2*v+1].lzy_mx += t[v].lzy_ad;
t[2*v].lzy_mx = max(t[2*v].lzy_mx, t[v].lzy_mx);
t[2*v+1].lzy_mx = max(t[2*v+1].lzy_mx, t[v].lzy_mx);
t[2*v].lzy_ad2 += t[v].lzy_ad2;
t[2*v+1].lzy_ad2 += t[v].lzy_ad2;
t[v].lzy_ad = t[v].lzy_ad2 = 0, t[v].lzy_mx = -INF;
}
void upd(int v, int tl, int tr, int l, int r, ll val){
push(v, tl, tr);
if (l <= tl && tr <= r) {
t[v].lzy_ad += val, t[v].lzy_mx += val;
if (val > 0) t[v].lzy_ad2 += val;
return;
}
int tm=(tl+tr)/2;
if (l <= tm)
upd(2*v, tl, tm, l, r, val);
if (r > tm)
upd(2*v+1, tm+1, tr, l, r, val);
}
ll qry(int v, int tl, int tr, int pos){
push(v, tl, tr);
if (tl == tr){
return t[v].lzy_ad2 - max(t[v].lzy_ad, t[v].lzy_mx);
}
int tm=(tl+tr)/2;
if (pos <= tm) return qry(2*v, tl, tm, pos);
else return qry(2*v+1, tm+1, tr, pos);
}
void ad(int l, int r, ll val){ upd(1, 0, n-1, l, r, val); }
void fix(){ t[1].lzy_mx = max(t[1].lzy_mx, 0ll); }
ll qry(int i){ return qry(1, 0, n-1, i); }
} bst;
vpl queries[N];
int ans[N];
int n, m, q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
vector<array<ll, 5>> que(q);
SumSeg sseg; sseg.init(n);
// SegmentTreeBeats<ll> seg; seg.init(n);
bst.init(n);
f0r(t, q) {
int ty; cin >> ty;
auto& qq = que[t];
ty--;
qq[0] = ty;
if (ty == 0) {
int l, r, c; ll k; cin >> l >> r >> c >> k;
l--, r--;
qq[1] = l;
qq[2] = r;
qq[3] = c;
qq[4] = k;
sseg.upd(l, r, k);
bst.ad(l, r, k);
// seg.upd(2, l, r, k);
} else if (ty == 1) {
int l, r; ll k; cin >> l >> r >> k;
l--, r--;
qq[1] = l;
qq[2] = r;
qq[3] = k;
// seg.upd(2, l, r, -k);
bst.ad(l, r, -k);
bst.fix();
// seg.upd(1, l, r, 0);
} else {
int a; ll b; cin >> a >> b;
a--;
qq[1] = a;
ll tt = sseg.query(a, a);
ll c = bst.qry(a);
ll amt;
amt = c + b;
qq[2] = amt;
queries[a].eb(amt, t);
}
}
f0r(i, n) sort(all(queries[i])), reverse(all(queries[i]));
MaxSeg mseg; mseg.init(n);
f0r(i, n) {
if (queries[i].empty()) {
mseg.upd(i, i, -2 * INF);
continue;
}
mseg.upd(i, i, -queries[i].back().f);
}
f0r(t, q) {
auto& qq = que[t];
int ty = qq[0];
if (ty == 0) {
int l = qq[1];
int r = qq[2];
int c = qq[3];
ll k = qq[4];
mseg.upd(l, r, k);
auto res = mseg.query(0, n - 1);
while (res.f >= 0) {
int loc = res.s;
auto done = queries[loc].back();
ans[done.s] = c;
mseg.upd(loc, loc, done.f);
queries[loc].pop_back();
if (!queries[loc].empty()) {
auto nxt = queries[loc].back();
mseg.upd(loc, loc, -nxt.f);
} else {
mseg.upd(loc, loc, -INF);
}
res = mseg.query(0, n - 1);
}
} else if (ty == 1) {
continue;
} else {
continue;
}
}
f0r(i, q) {
if (que[i][0] != 2) continue;
cout << ans[i] << '\n';
}
return 0;
}
/**
* So basically, we can reindex the person, so we want to find the first point in time you have >= x customers at shop i
*
*/
Compilation message
foodcourt.cpp: In member function 'void SegmentTreeBeats<C>::upd(int, int, int, C, int, int, int)':
foodcourt.cpp:235:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
235 | if (t == 0)
| ^
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:414:16: warning: unused variable 'tt' [-Wunused-variable]
414 | ll tt = sseg.query(a, a);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
44144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1029 ms |
68308 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
230 ms |
44068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
