/**
____ ____ ____ ____ ____ ____
||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;
add_query(int _l, int _r, int _c, ll _k)
{
l = _l;
r = _r;
c = _c;
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;
add_query aq(l, r, c, k);
vq.push_back(aq);
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: In function 'void solve()':
foodcourt.cpp:244:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<add_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
244 | for (int i = 0; i < vq.size(); i ++)
| ~~^~~~~~~~~~~
foodcourt.cpp:256: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]
256 | if (ptr[pos] != ask[pos].size() - 1)
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
53324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
53324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
57976 KB |
Output is correct |
| 2 |
Correct |
111 ms |
58176 KB |
Output is correct |
| 3 |
Incorrect |
96 ms |
57928 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
582 ms |
74928 KB |
Output is correct |
| 2 |
Correct |
496 ms |
72516 KB |
Output is correct |
| 3 |
Correct |
639 ms |
75912 KB |
Output is correct |
| 4 |
Correct |
555 ms |
73336 KB |
Output is correct |
| 5 |
Correct |
563 ms |
73240 KB |
Output is correct |
| 6 |
Correct |
756 ms |
76844 KB |
Output is correct |
| 7 |
Correct |
103 ms |
62340 KB |
Output is correct |
| 8 |
Correct |
108 ms |
62076 KB |
Output is correct |
| 9 |
Correct |
846 ms |
77700 KB |
Output is correct |
| 10 |
Correct |
732 ms |
78008 KB |
Output is correct |
| 11 |
Correct |
634 ms |
75948 KB |
Output is correct |
| 12 |
Correct |
651 ms |
76020 KB |
Output is correct |
| 13 |
Correct |
629 ms |
75928 KB |
Output is correct |
| 14 |
Correct |
596 ms |
75968 KB |
Output is correct |
| 15 |
Correct |
602 ms |
75868 KB |
Output is correct |
| 16 |
Correct |
623 ms |
76000 KB |
Output is correct |
| 17 |
Correct |
642 ms |
75940 KB |
Output is correct |
| 18 |
Correct |
615 ms |
75884 KB |
Output is correct |
| 19 |
Correct |
624 ms |
75984 KB |
Output is correct |
| 20 |
Correct |
636 ms |
75844 KB |
Output is correct |
| 21 |
Correct |
596 ms |
75888 KB |
Output is correct |
| 22 |
Correct |
601 ms |
75828 KB |
Output is correct |
| 23 |
Correct |
627 ms |
75984 KB |
Output is correct |
| 24 |
Correct |
615 ms |
75912 KB |
Output is correct |
| 25 |
Correct |
457 ms |
75284 KB |
Output is correct |
| 26 |
Correct |
487 ms |
75776 KB |
Output is correct |
| 27 |
Incorrect |
470 ms |
76012 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
53324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
153 ms |
59252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
53324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
53324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
