/* In the name of GOD */
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mk make_pair
typedef long long ll;
typedef long double ld;
#define int ll
typedef pair <long long, long long> pii;
const int N = 250012, SegN = (1 << 19);
const long long INF = 1e18 + 31;
pii lz[SegN];
ll slz[SegN];
int t[N], l[N], r[N], c[N], ans[N];
ll k[N], x[N];
vector <pair <ll, int>> v[N];
vector <pair <int, int>> s[N], e[N];
ll LZ[SegN];
ll MX[SegN];
void SHIFT (int v) {
if (!LZ[v])
return;
LZ[v << 1] += LZ[v];
LZ[v << 1 | 1] += LZ[v];
MX[v << 1] += LZ[v];
MX[v << 1 | 1] += LZ[v];
LZ[v] = 0;
}
void ADD (int l, int r, int x, int v = 1, int tl = 0, int tr = N - 1) {
if (tl > r || l > tr)
return;
if (l <= tl && tr <= r) {
LZ[v] += x;
MX[v] += x;
} else {
SHIFT(v);
int mid = (tl + tr) >> 1;
ADD (l, r, x, v << 1, tl, mid);
ADD (l, r, x, v << 1 | 1, mid + 1, tr);
MX[v] = max(MX[v << 1], MX[v << 1 | 1]);
}
}
int GET (int x, int v = 1, int tl = 0, int tr = N - 1) {
if (x == -1)
return 0;
if (tl == tr) {
return c[tl];
}
SHIFT(v);
int mid = (tl + tr) >> 1;
if (MX[v << 1] >= x) {
return GET (x, v << 1, tl, mid);
} else {
return GET (x, v << 1 | 1, mid + 1, tr);
}
}
void shift (int v) {
ll x = lz[v].F, y = lz[v].S;
lz[v << 1].F += x;
lz[v << 1].S += x;
lz[v << 1 | 1].F += x;
lz[v << 1 | 1].S += x;
lz[v << 1].S = max(lz[v << 1].S, y);
lz[v << 1 | 1].S = max(lz[v << 1 | 1].S, y);
slz[v << 1] += slz[v];
slz[v << 1 | 1] += slz[v];
lz[v] = mk(0, 0);
slz[v] = 0;
}
void add (int l, int r, int x, int v = 1, int tl = 0, int tr = N - 1) {
// cout << l << ' ' << r << ' ' << x << ' ' << v << ' ' << tl << ' ' << tr << '\n';
if (tl > r || l > tr)
return;
if (l <= tl && tr <= r) {
//cout << "wef\n";
slz[v] += max(0, x);
lz[v].S += x;
lz[v].F += x;
//cout << lz[v].F << ' ' << lz[v].S << '\n';
} else {
shift(v);
int mid = (tl + tr) >> 1;
add (l, r, x, v << 1, tl, mid);
add (l, r, x, v << 1 | 1, mid + 1, tr);
}
}
pii get (int i, int v = 1, int tl = 0, int tr = N - 1) {
if (tl == tr)
return mk(slz[v], max(lz[v].F, lz[v].S));
shift(v);
int mid = (tl + tr) >> 1;
if (i <= mid)
return get (i, v << 1, tl, mid);
return get (i, v << 1 | 1, mid + 1, tr);
}
int32_t main () {
ios::sync_with_stdio(false);
cin.tie();
for (int v = 0; v < SegN; v++)
lz[v] = mk(0, 0);
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < q; i++) {
ans[i] = -1;
cin >> t[i];
if (t[i] == 1) {
cin >> l[i] >> r[i] >> c[i] >> k[i];
s[l[i]].push_back(mk(i, k[i]));
e[r[i]].push_back(mk(i, k[i]));
add (l[i], r[i], k[i]);
} else if (t[i] == 2) {
cin >> l[i] >> r[i] >> k[i];
add (l[i], r[i], -k[i]);
} else {
cin >> l[i] >> k[i];
pii p = get (l[i]);
if (k[i] > p.S) {
x[i] = -1;
} else {
x[i] = p.F - p.S + k[i];
}
v[l[i]].push_back(mk(x[i], i));
}
}
// FFFFFFFFFFFFFFFINALY
for (int i = 1; i <= n; i++) {
for (auto [tt, kk] : s[i]) {
ADD (tt, N - 1, kk);
}
for (auto [j, ii] : v[i])
ans[ii] = GET (j);
for (auto [tt, kk] : e[i]) {
ADD (tt, N - 1, -kk);
}
}
for (int i = 0; i < q; i++) {
if (ans[i] >= 0)
cout << ans[i] << '\n';
}
}
Compilation message
foodcourt.cpp: In function 'void add(ll, ll, ll, ll, ll, ll)':
foodcourt.cpp:85:21: error: no matching function for call to 'max(int, ll&)'
85 | slz[v] += max(0, x);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from foodcourt.cpp:3:
/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:85:21: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
85 | slz[v] += max(0, x);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from foodcourt.cpp:3:
/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:85:21: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
85 | slz[v] += max(0, x);
| ^
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:3:
/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:85:21: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
85 | slz[v] += max(0, x);
| ^
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:3:
/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:85:21: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
85 | slz[v] += max(0, x);
| ^
foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:138:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
138 | for (auto [tt, kk] : s[i]) {
| ^
foodcourt.cpp:141:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
141 | for (auto [j, ii] : v[i])
| ^
foodcourt.cpp:143:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
143 | for (auto [tt, kk] : e[i]) {
| ^
