#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace SegmentTree {
constexpr int N_ = 1 << 19;
pair<ll, ll> t[N_]; // f(x) = max(0, x - t[i].first) + t[i].second
int sz = 1;
void init(int n) {
sz = 1 << __lg(n) + !!(n & (n - 1));
}
void apply(int x, pair<ll, ll> d) {
if (t[x].second >= d.first) {
t[x] = {t[x].first, t[x].second - d.first + d.second};
} else {
t[x] = {t[x].first + d.first - t[x].second, d.second};
}
}
void push(int x) {
if (t[x].first || t[x].second) {
apply(x << 1, t[x]), apply(x << 1 | 1, t[x]);
t[x] = {};
}
}
void rangeApply(int l, int r, pair<ll, ll> a, int x = 1, int lx = 0, int rx = sz) {
if (l >= rx || lx >= r) {
return;
}
if (l <= lx && rx <= r) {
return apply(x, a);
}
push(x);
int mid = lx + rx >> 1;
rangeApply(l, r, a, x << 1, lx, mid), rangeApply(l, r, a, x << 1 | 1, mid, rx);
}
ll query(int x) {
ll d = 0;
for (x += sz; x > 1; x >>= 1) {
d = max(0LL, d - t[x].first) + t[x].second;
}
return d;
}
}
namespace SegmentTreeMin {
constexpr int N_ = 1 << 19;
pair<ll, int> t[N_]; // f(x) = max(0, x - t[i].first) + t[i].second
ll tag[N_];
int sz = 1;
void init(int n) {
sz = 1 << __lg(n) + !!(n & (n - 1));
for (int i = 0; i < sz; ++i) {
t[i + sz] = {i < n ? 0 : 3e18, i};
}
for (int i = sz - 1; i > 0; --i) {
t[i] = min(t[i << 1], t[i << 1 | 1]);
}
}
void apply(int x, ll d) {
tag[x] += d, t[x].first += d;
}
void rangeAdd(int l, int r, ll a, int x = 1, int lx = 0, int rx = sz) {
if (l >= rx || lx >= r) {
return;
}
if (l <= lx && rx <= r) {
return apply(x, a);
}
int mid = lx + rx >> 1;
rangeAdd(l, r, a, x << 1, lx, mid), rangeAdd(l, r, a, x << 1 | 1, mid, rx);
t[x] = min(t[x << 1], t[x << 1 | 1]);
t[x].first += tag[x];
}
pair<ll, int> top() {
return t[1];
}
}
template<typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick() = default;
explicit Fenwick(int n) : n(n), a(n + 1) {}
void modify(int x, T v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i] += v;
}
}
void modify(int l, int r, T v) {
if (l >= r) return;
modify(l, v), modify(r, -v);
}
T sum(int x) {
T ans = 0;
for (int i = x + 1; i > 0; i -= i & -i) {
ans += a[i];
}
return ans;
}
};
constexpr int N = 2.5e5 + 10;
vector<pair<ll, int>> que[N];
int pnt[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
struct Query {
int t, l, r, c;
ll k;
};
vector<Query> queries(q);
Fenwick<ll> fn(n), fnAdd(n);
SegmentTree::init(n);
SegmentTreeMin::init(n);
vector<ll> ans(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].t;
if (queries[i].t == 1) {
cin >> queries[i].l >> queries[i].r >> queries[i].c >> queries[i].k;
} else if (queries[i].t == 2) {
cin >> queries[i].l >> queries[i].r >> queries[i].k;
} else {
cin >> queries[i].l >> queries[i].k;
}
queries[i].l -= 1;
if (queries[i].t == 1) {
SegmentTree::rangeApply(queries[i].l, queries[i].r, {0, queries[i].k});
fnAdd.modify(queries[i].l, queries[i].r, queries[i].k);
} else if (queries[i].t == 2) {
SegmentTree::rangeApply(queries[i].l, queries[i].r, {queries[i].k, 0});
fn.modify(queries[i].l, queries[i].r, queries[i].k);
} else {
ll s = fn.sum(queries[i].l);
ll have = SegmentTree::query(queries[i].l) + s;
ll need = queries[i].k + s;
if (have >= need) {
que[queries[i].l].emplace_back(fnAdd.sum(queries[i].l) - (have - s - queries[i].k), i);
}
}
}
auto relax = [&](int i) {
if (pnt[i] == que[i].size()) {
SegmentTreeMin::rangeAdd(i, i + 1, 3e18);
} else {
SegmentTreeMin::rangeAdd(i, i + 1, que[i][pnt[i]].first - (pnt[i] == 0 ? 0 : que[i][pnt[i] - 1].first));
}
};
for (int i = 0; i < n; ++i) {
sort(que[i].begin(), que[i].end());
relax(i);
}
for (int i = 0; i < q; ++i) {
if (queries[i].t == 1) {
SegmentTreeMin::rangeAdd(queries[i].l, queries[i].r, -queries[i].k);
}
while (SegmentTreeMin::t[1].first <= 0) {
int j = SegmentTreeMin::t[1].second;
ans[que[j][pnt[j]].second] = queries[i].c;
++pnt[j];
relax(j);
}
}
for (int i = 0; i < q; ++i) {
if (queries[i].t == 3) {
cout << ans[i] << '\n';
}
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'void SegmentTree::init(int)':
foodcourt.cpp:13:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
13 | sz = 1 << __lg(n) + !!(n & (n - 1));
| ~~~~~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'void SegmentTree::rangeApply(int, int, std::pair<long long int, long long int>, int, int, int)':
foodcourt.cpp:39:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid = lx + rx >> 1;
| ~~~^~~~
foodcourt.cpp: In function 'void SegmentTreeMin::init(int)':
foodcourt.cpp:60:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
60 | sz = 1 << __lg(n) + !!(n & (n - 1));
| ~~~~~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'void SegmentTreeMin::rangeAdd(int, int, ll, int, int, int)':
foodcourt.cpp:80:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int mid = lx + rx >> 1;
| ~~~^~~~
foodcourt.cpp: In lambda function:
foodcourt.cpp:174:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | if (pnt[i] == que[i].size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6472 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6480 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
6228 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6472 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6480 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
6228 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
15520 KB |
Output is correct |
| 2 |
Correct |
114 ms |
15536 KB |
Output is correct |
| 3 |
Correct |
80 ms |
15548 KB |
Output is correct |
| 4 |
Correct |
88 ms |
15532 KB |
Output is correct |
| 5 |
Correct |
89 ms |
15636 KB |
Output is correct |
| 6 |
Correct |
83 ms |
15564 KB |
Output is correct |
| 7 |
Incorrect |
32 ms |
8756 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
490 ms |
39680 KB |
Output is correct |
| 2 |
Correct |
392 ms |
35288 KB |
Output is correct |
| 3 |
Correct |
508 ms |
42244 KB |
Output is correct |
| 4 |
Correct |
410 ms |
38388 KB |
Output is correct |
| 5 |
Correct |
412 ms |
34620 KB |
Output is correct |
| 6 |
Correct |
613 ms |
41728 KB |
Output is correct |
| 7 |
Incorrect |
97 ms |
14936 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6472 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6480 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
6228 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
16352 KB |
Output is correct |
| 2 |
Correct |
124 ms |
16156 KB |
Output is correct |
| 3 |
Correct |
148 ms |
16928 KB |
Output is correct |
| 4 |
Correct |
92 ms |
15528 KB |
Output is correct |
| 5 |
Correct |
101 ms |
16336 KB |
Output is correct |
| 6 |
Correct |
116 ms |
16968 KB |
Output is correct |
| 7 |
Incorrect |
32 ms |
9172 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6472 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6480 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
6228 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6472 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6480 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
8 ms |
6484 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
6228 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
