/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 250010;
const ll inf = 1e17;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct segment_tree_modified
{
pair < ll, ll > lazy[4 * maxn];
ll tree[4 * maxn];
pair < ll, ll > merge_lazy(pair < ll, ll > p1, pair < ll, ll > p2)
{
if (p1.second > p2.first)
{
return {p1.first, p1.second - p2.first + p2.second};
}
else
{
return {p1.first - p1.second + p2.first, p2.second};
}
}
void push_lazy(int root, int left, int right)
{
if (left == right)
{
tree[root] = max((ll)(0), tree[root] - lazy[root].first) + lazy[root].second;
}
else
{
lazy[root * 2] = merge_lazy(lazy[root * 2], lazy[root]);
lazy[root * 2 + 1] = merge_lazy(lazy[root * 2 + 1], lazy[root]);
}
lazy[root] = {0, 0};
}
void range_update(int root, int left, int right, int qleft, int qright,
pair < ll, ll > val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
range_update(root * 2, left, mid, qleft, qright, val);
range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
ll query(int root, int left, int right, int idx)
{
///cout << left << " - " << right << " " << lazy[root].first << " " << lazy[root].second << endl;
push_lazy(root, left, right);
if (left == right)
return tree[root];
int mid = (left + right) /2;
if (idx <= mid)
return query(root * 2, left, mid, idx);
return query(root * 2 + 1, mid + 1, right, idx);
}
};
struct node
{
ll minx, min_idx;
node()
{
minx = inf;
}
};
node merge_nodes(node nd1, node nd2)
{
if (nd1.minx < nd2.minx)
return nd1;
return nd2;
}
struct segment_tree
{
ll lazy[4 * maxn];
node tree[4 * maxn];
void push_lazy(int root, int left, int right)
{
tree[root].minx += lazy[root];
if (left == right)
tree[root].min_idx = left;
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void range_update(int root, int left, int right,
int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] += val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
range_update(root * 2, left, mid, qleft, qright, val);
range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
void point_update(int root, int left, int right, int idx, ll val)
{
push_lazy(root, left, right);
if (left == right)
{
tree[root].minx = val;
tree[root].min_idx = left;
return;
}
int mid = (left + right) / 2;
if (idx <= mid)
point_update(root * 2, left, mid, idx, val);
else
point_update(root * 2 + 1, mid + 1, right, idx, val);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
};
struct add_query
{
int l, r, c;
ll k;
query(int _l, int _r, ll _k)
{
l = _l;
r = _r;
k = _k;
}
};
segment_tree_modified real_val, add_only;
segment_tree st;
int n, m, q, ans[maxn], ptr[maxn], tf[maxn];
vector < pair < int, int > > ask[maxn];
void solve()
{
cin >> n >> m >> q;
vector < add_query > vq;
for (int i = 1; i <= q; i ++)
{
int type;
cin >> type;
if (type == 1)
{
int l, r, c;
ll k;
cin >> l >> r >> c >> k;
vq.push_back({l, r, c, k});
real_val.range_update(1, 1, n, l, r, {0, k});
add_only.range_update(1, 1, n, l, r, {0, k});
}
else if (type == 2)
{
int l, r;
ll k;
cin >> l >> r >> k;
real_val.range_update(1, 1, n, l, r, {k, 0});
}
else
{
int a;
ll b;
tf[i] = 1;
cin >> a >> b;
ll val1 = real_val.query(1, 1, n, a);
ll val2 = add_only.query(1,1,n, a);
if (val1 >= b)
{
ll idx = val2 - val1 + b;
ask[a].push_back({idx, i});
}
}
}
for (int i = 1; i <= n; i ++)
sort(ask[i].begin(), ask[i].end());
for (int i = 1; i <= n; i ++)
{
ll val = inf;
if (!ask[i].empty())
val = ask[i][0].first;
st.point_update(1, 1, n, i, val);
}
for (int i = 0; i < vq.size(); i ++)
{
add_query aq = vq[i];
st.range_update(1, 1, n, aq.l, aq.r, - aq.k);
while(true)
{
node nd = st.tree[1];
if (nd.minx > 0)
break;
int pos = nd.min_idx;
ans[ask[pos][ptr[pos]].second] = aq.c;
ll val = inf;
if (ptr[pos] != ask[pos].size() - 1)
{
val = ask[pos][ptr[pos] + 1].first
- ask[pos][ptr[pos]].first;
}
st.point_update(1, 1, n, nd.min_idx, val + nd.minx);
ptr[pos] ++;
}
}
for (int i = 1; i <= q; i ++)
if (tf[i])
cout << ans[i] << endl;
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
foodcourt.cpp:177:5: error: ISO C++ forbids declaration of 'query' with no type [-fpermissive]
177 | query(int _l, int _r, ll _k)
| ^~~~~
foodcourt.cpp: In member function 'int add_query::query(int, int, ll)':
foodcourt.cpp:182:5: warning: no return statement in function returning non-void [-Wreturn-type]
182 | }
| ^
foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:242:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<add_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
242 | for (int i = 0; i < vq.size(); i ++)
| ~~^~~~~~~~~~~
foodcourt.cpp:254:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
254 | if (ptr[pos] != ask[pos].size() - 1)
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
