#include "bits/stdc++.h"
using namespace std;
template<class T>struct fenwick {
vector<T> bit;
fenwick(int n) {
bit.assign(n + 5, 0);
}
void add(int i, T delta) {
for (; i < (int)bit.size(); i += i & -i)
bit[i] += delta;
}
T query(int i) {
T ans = 0;
for (; i; i -= i & -i) {
ans += bit[i];
}
return ans;
}
};
template<class T>class lazy_segtree {
private:
vector<T> st, lz;
int n;
#define lc id << 1
#define rc id << 1 | 1
void push(int id, int l, int r) {
st[id] += lz[id];
if (l != r) {
lz[lc] += lz[id];
lz[rc] += lz[id];
}
lz[id] = 0;
}
void modify(int L, int R, T val, int id, int l, int r) {
if (R < l || r < L) return;
push(id, l, r);
if (L <= l && r <= R) {
lz[id] += val;
push(id, l, r);
return;
}
int mid = (l + r) / 2;
modify(L, R, val, lc, l, mid);
modify(L, R, val, rc, mid + 1, r);
st[id] = min(st[lc], st[rc]);
}
T getmin(int id, int l, int r, int L, int R)
{
push(id, l, r);
if (l > R || L > r) return LLONG_MAX;
if (L <= l && r <= R) return st[id];
int mid = (l + r) / 2;
return min(getmin(lc, l, mid, L, R), getmin(rc, mid + 1, r, L, R));
}
int findfirst(T value, int id, int l, int r) {
/// find first position a[x] < value
push(id, l, r);
if (st[id] > value) return -1;
if (l == r) return l;
int mid = (l + r) / 2;
push(lc, l, mid); push(rc, mid + 1, r);
if (st[lc] <= value) return findfirst(value, lc, l, mid);
else return findfirst(value, rc, mid + 1, r);
}
public:
void modify(int L, int R, T val) {
modify(L, R, val, 1, 1, n);
}
T getmin(int L, int R) {
return getmin(1, 1, n, L, R);
}
int findfirst(T val) {
return findfirst(val, 1, 1, n);
}
lazy_segtree(int _n) {
n = _n;
st.assign(4 * n + 5, 0);
lz.assign(4 * n + 5, 0);
}
};
template<class T>class segtree_beat {
/// modify: segtree_beat operator
/// get: query single index
private:
const int64_t inf = 1e18;
vector<T> st, lazy;
int size;
#define lc id << 1
#define rc id << 1 | 1
void apply(int id, T add, T bound) {
st[id] = max(bound, st[id] + add);
lazy[id] += add;
}
void push(int id, int ok) {
if (ok) {
//cerr << "apply" << ' ' << lazy[id] << ' ' << st[id] << '\n';
apply(lc, lazy[id], st[id]);
apply(rc, lazy[id], st[id]);
}
lazy[id] = 0;
st[id] = -inf;
}
void modify(int L, int R, T val, int id, int l, int r) {
if (R < l or r < L) return;
if (L <= l and r <= R) {
apply(id, val, -inf);
} else {
push(id, (l != r));
int mid = (l + r) / 2;
modify(L, R, val, lc, l, mid);
modify(L, R, val, rc, mid + 1, r);
}
}
T get(int pos, int id, int l, int r) {
if (l == r)
return st[id];
push(id, (l != r));
/// cerr << "debug" << st[lc] << ' ' << st[rc] << ' ' << lazy[id] << '\n';
int mid = (l + r) / 2;
if (pos <= mid) return get(pos, lc, l, mid);
else return get(pos, rc, mid + 1, r);
}
public:
segtree_beat(int n) {
size = n;
st.resize(4 * size, 0);
lazy.resize(4 * size, 0);
}
void modify(int L, int R, T val) {
/// a[x] = max(0, a[x] += val);
modify(L, R, val, 1, 1, size);
apply(1, 0, 0);
}
T get(int pos) {
return get(pos, 1, 1, size);
}
void debug(int id, int l, int r) {
cerr << l << ' ' << r << ' ' << st[id] << ' ' << lazy[id] << '\n';
if (l == r) return;
int mid = (l + r) / 2;
debug(lc, l, mid); debug(rc, mid + 1, r);
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M, Q; cin >> N >> M >> Q;
fenwick<int64_t> tot(N + 5);
segtree_beat<int64_t> cur(N);
vector<tuple<int, int64_t, int64_t, int64_t, int64_t>> queries(Q);
vector<vector<pair<int64_t, int>>> ask(N + 5);
for (int i = 0; i < Q; ++i) {
auto &[op, a, b, c, k] = queries[i];
cin >> op;
if (op == 1) {
cin >> a >> b >> c >> k;
tot.add(a, k);tot.add(b + 1, -k);
cur.modify(a, b, k);
} else if (op == 2) {
cin >> a >> b >> k;
cur.modify(a, b, -k);
} else {
cin >> a >> b;
int64_t t = tot.query(a);
int64_t c = cur.get(a);
if (b <= c) {
ask[a].emplace_back(t - (c - b), i);
}
}
#ifdef LOCAL
for (int j = 1; j <= N; ++j) {
cerr << cur.get(j) << ' ';
}
cerr << '\n';
#endif
}
vector<int> ans(Q), inds(N + 5);
lazy_segtree<int64_t> groups(N);
for (int i = 1; i <= N; ++i) {
if (ask[i].empty()) {
groups.modify(i, i, (int64_t)1e17);
} else {
sort(ask[i].begin(), ask[i].end());
groups.modify(i, i, ask[i][0].first);
}
}
for (int i = 0; i < Q; ++i) {
auto &[op, a, b, c, k] = queries[i];
if (op == 1) {
groups.modify(a, b, -k);
while (true) {
int pos = groups.findfirst(0);
if (pos == -1 or pos > N) break;
ans[ask[pos][inds[pos]].second] = c;
++inds[pos];
if (inds[pos] == ask[pos].size()) groups.modify(pos, pos, (int64_t)1e17);
else groups.modify(pos, pos, ask[pos][inds[pos]].first -
ask[pos][inds[pos] - 1].first);
}
}
}
for (int i = 0; i < Q; ++i) {
if (get<0>(queries[i]) == 3) cout << ans[i] << '\n';
}
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:158:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
158 | auto &[op, a, b, c, k] = queries[i];
| ^
foodcourt.cpp:193:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
193 | auto &[op, a, b, c, k] = queries[i];
| ^
foodcourt.cpp:201:23: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | if (inds[pos] == ask[pos].size()) groups.modify(pos, pos, (int64_t)1e17);
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
14712 KB |
Output is correct |
| 2 |
Incorrect |
87 ms |
14808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
440 ms |
52052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
15040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
