// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
using ll = int64_t;
using T = array<ll, 2>;
struct Seg {
vector<ll> suf, pos, all; int N;
void init(int n) {
N = 1; while(N < n) N *= 2;
suf.assign(2*N, 0); pos.assign(2*N, 0); all.assign(2*N, 0);
}
void pull(int p) {
pos[p] = pos[2*p] + pos[2*p+1];
all[p] = all[2*p] + all[2*p+1];
suf[p] = max(suf[2*p] + all[2*p+1], suf[2*p+1]);
}
void upd(int p, ll v, int x, int L, int R) {
if (p < L || R < p) return;
if (L == R) {
suf[x] = all[x] = v;
pos[x] = max(v, 0LL);
return;
}
int M = (L+R)/2;
upd(p, v, 2*x, L, M); upd(p, v, 2*x+1, M+1, R);
pull(x);
}
T max_suf(int l, int r, int x, int L, int R) {
if (r < L || R < l) return T{0, 0};
if (l <= L && R <= r) return T{suf[x], all[x]};
int M = (L+R)/2;
T a = max_suf(l, r, 2*x, L, M), b = max_suf(l, r, 2*x+1, M+1, R);
return {max(a[0] + b[1], b[0]), a[1] + b[1]};
};
ll sum_pos(int l, int r, int x, int L, int R) {
if (r < L || R < l) return 0;
if (l <= L && R <= r) return pos[x];
int M = (L+R)/2;
return sum_pos(l, r, 2*x, L, M) + sum_pos(l, r, 2*x+1, M+1, R);
}
int walk(int l, int r, ll v, ll V, int x, int L, int R) {
// cout << x << " " << L << " " << R << " " << V << endl;
// cout << l << " " << r << " " << v << endl;
if (r < L || R < l || v > V) return -1;
if (L == R) return L;
int M = (L+R)/2;
int res = walk(l, r, v, V - pos[2*x+1], 2*x, L, M);
if (res == -1) return walk(l, r, v, V, 2*x+1, M+1, R);
return res;
}
void upd(int p, int x) { upd(p, x, 1, 0, N-1); }
T max_suf(int l, int r) { return max_suf(l, r, 1, 0, N-1); }
ll sum_pos(int l, int r) { return sum_pos(l, r, 1, 0, N-1); }
ll walk(int l, int r, ll v) { return walk(l, r, v, pos[1], 1, 0, N-1); }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, Q; cin >> N >> M >> Q;
vector<vector<int>> QL(N), QR(N), QQ(N);
vector<ll> C(Q), K(Q);
for(int q = 0; q < Q; q++) {
int t; cin >> t;
if (t == 1) {
int l, r; cin >> l >> r >> C[q] >> K[q]; --l, --r;
QL[l].push_back(q);
QR[r].push_back(q);
}
if (t == 2) {
int l, r; cin >> l >> r >> K[q]; --l, --r;
K[q] = -K[q], C[q] = -1;
QL[l].push_back(q);
QR[r].push_back(q);
}
if (t == 3) {
int i; cin >> i >> K[q]; --i;
QQ[i].push_back(q);
}
}
Seg st; st.init(Q);
vector<ll> ans(Q, -1);
for(int i = 0; i < N; i++) {
for(auto q : QL[i]) { st.upd(q, K[q]);/* cout << "ON: " << q << endl;*/ }
for(auto q : QQ[i]) {
ll pos = st.sum_pos(0, q), suf = st.max_suf(0, q)[0];
ll I = pos - suf + K[q];
// cout << "INFO: " << q << " " << pos << " " << suf << " " << I << endl;
int res = st.walk(0, q, I);
assert(res == -1 || res <= q);
ans[q] = (res == -1 ? 0 : C[res]);
// cout << "DONE: " << res << endl;
}
for(auto q : QR[i]) { st.upd(q, 0); /*cout << "OFF: " << q << endl;*/ }
}
for(int q = 0; q < Q; q++) if (ans[q] != -1) cout << ans[q] << nl;
return 0;
}
Compilation message
foodcourt.cpp: In member function 'void Seg::upd(int, ll, int, int, int)':
foodcourt.cpp:30:23: error: no matching function for call to 'max(ll&, long long int)'
30 | pos[x] = max(v, 0LL);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from foodcourt.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
foodcourt.cpp:30:23: note: deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
30 | pos[x] = max(v, 0LL);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from foodcourt.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
foodcourt.cpp:30:23: note: deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
30 | pos[x] = max(v, 0LL);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from foodcourt.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
foodcourt.cpp:30:23: note: mismatched types 'std::initializer_list<_Tp>' and 'long int'
30 | pos[x] = max(v, 0LL);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from foodcourt.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
foodcourt.cpp:30:23: note: mismatched types 'std::initializer_list<_Tp>' and 'long int'
30 | pos[x] = max(v, 0LL);
| ^
