#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 250000 + 10;
const llong INF = 1e18;
int n, m, q;
struct SegmentTree
{
struct Node
{
llong minPrefix;
llong maxSuffix;
llong sumPositive;
llong sumNegative;
llong sum;
int c;
Node()
{
maxSuffix = minPrefix = sumPositive = sumNegative = sum = c = 0;
}
friend Node operator + (const Node &left, const Node &right)
{
Node res;
res.sum = left.sum + right.sum;
res.sumPositive = left.sumPositive + right.sumPositive;
res.sumNegative = left.sumNegative + right.sumNegative;
res.minPrefix = std::min(left.minPrefix, left.sum + right.minPrefix);
res.maxSuffix = std::max(right.maxSuffix, right.sum + left.maxSuffix);
res.c = std::max(left.c, right.c);
return res;
}
};
Node tree[4*MAXN];
void update(int l, int r, int node, int queryPos, int queryVal, int queryC, bool queryType)
{
if (l == r)
{
tree[node].c = queryC;
if (queryType == true)
{
tree[node].sum = queryVal;
tree[node].sumNegative = 0;
tree[node].sumPositive = queryVal;
} else
{
tree[node].sum = -queryVal;
tree[node].sumPositive = 0;
tree[node].sumNegative = queryVal;
}
tree[node].minPrefix = tree[node].sum;
tree[node].maxSuffix = tree[node].sum;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal, queryC, queryType);
else update(mid + 1, r, 2*node + 1, queryPos, queryVal, queryC, queryType);
tree[node] = tree[2*node] + tree[2*node + 1];
}
Node query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
Node res;
int mid = (l + r) / 2;
if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) res = res + query(mid + 1, r, 2*node + 1, queryL, queryR);
return res;
}
llong find(int l, int r, int node, int queryL, int queryR, llong k)
{
std::cout << "find: " << l << ' ' << r << ' ' << node << ' ' << tree[node].sumPositive << ' ' << k << '\n';
if (queryR < l || r < queryL)
{
return 0;
}
if (queryL <= l && r <= queryR && tree[node].sumPositive < k)
{
return -tree[node].sumPositive;
}
if (l == r)
{
return tree[node].c;
}
int mid = (l + r) / 2;
llong res = find(l, mid, 2*node, queryL, queryR, k);
if (res > 0) return res;
llong res2 = find(mid + 1, r, 2*node + 1, queryL, queryR, k + res);
if (res2 > 0) return res2;
else return res + res2;
}
void update(int pos, int val, int c, bool type)
{
update(1, q, 1, pos, val, c, type);
}
Node query(int l, int r)
{
return query(1, q, 1, l, r);
}
int find(int l, int r, llong k)
{
return find(1, q, 1, l, r, k);
}
};
struct QueryAsk
{
int time;
llong val;
int idx;
};
struct QueryAdd
{
bool type;
int val;
int c;
int idx;
};
int cntServices;
std::vector <QueryAdd> activate[MAXN];
std::vector <QueryAdd> deactivate[MAXN];
std::vector <QueryAsk> v[MAXN];
SegmentTree tree;
int answer[MAXN];
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
for (const QueryAdd query : activate[i])
{
tree.update(query.idx, query.val, query.c, query.type);
}
for (const QueryAdd query : deactivate[i])
{
tree.update(query.idx, 0, 0, false);
}
for (const auto &[time, val, idx] : v[i])
{
int l = 0, r = time + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
llong res = tree.query(mid, time).minPrefix;
if (mid > 1) res += tree.query(1, mid - 1).maxSuffix;
if (res >= 0) r = mid;
else l = mid;
}
if (r > time)
{
answer[idx] = 0;
continue;
}
llong cntPositive = tree.query(r, time).sumPositive;
llong cntNegative = tree.query(r, time).sumNegative;
assert(tree.query(r, time).minPrefix >= 0);
if (val + cntNegative > cntPositive) answer[idx] = 0;
else
{
int start = r;
l = start - 1; r = time + 1;
while (l < r - 1)
{
mid = (l + r) / 2;
llong pos = tree.query(start, mid).sumPositive;
if (pos < cntNegative + val) l = mid;
else r = mid;
}
assert(r != time + 1);
answer[idx] = tree.query(r, r).c;
assert(answer[idx] != 0);
}
}
}
}
void input()
{
std::cin >> n >> m >> q;
for (int i = 1 ; i <= q ; ++i)
{
int qType;
std::cin >> qType;
if (qType == 1)
{
int l, r, c, val;
std::cin >> l >> r >> c >> val;
activate[l].push_back({true, val, c, i});
deactivate[r + 1].push_back({true, val, c, i});
continue;
}
if (qType == 2)
{
int l, r, c, val;
std::cin >> l >> r >> val;
activate[l].push_back({false, val, 0, i});
deactivate[r + 1].push_back({false, val, 0, i});
continue;
}
assert(qType == 3);
int pos;
llong k;
std::cin >> pos >> k;
v[pos].push_back({i, k, ++cntServices});
}
}
void print()
{
for (int i = 1 ; i <= cntServices ; ++i)
{
std::cout << answer[i] << '\n';
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}
Compilation message
foodcourt.cpp: In function 'void input()':
foodcourt.cpp:222:23: warning: unused variable 'c' [-Wunused-variable]
222 | int l, r, c, val;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
133200 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
133200 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
69900 KB |
Output is correct |
| 2 |
Correct |
197 ms |
69844 KB |
Output is correct |
| 3 |
Incorrect |
222 ms |
69712 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
297 ms |
158292 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
133200 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
69584 KB |
Output is correct |
| 2 |
Correct |
357 ms |
69748 KB |
Output is correct |
| 3 |
Correct |
380 ms |
69816 KB |
Output is correct |
| 4 |
Correct |
247 ms |
68896 KB |
Output is correct |
| 5 |
Correct |
313 ms |
69384 KB |
Output is correct |
| 6 |
Correct |
376 ms |
69896 KB |
Output is correct |
| 7 |
Correct |
267 ms |
68612 KB |
Output is correct |
| 8 |
Correct |
264 ms |
68544 KB |
Output is correct |
| 9 |
Correct |
341 ms |
69048 KB |
Output is correct |
| 10 |
Correct |
246 ms |
68688 KB |
Output is correct |
| 11 |
Correct |
349 ms |
69456 KB |
Output is correct |
| 12 |
Correct |
367 ms |
69484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
133200 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
133200 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
