#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
typedef long long llong;
const int MAXN = 250000 + 10;
const llong INF = 1e18;
const int BUFF_SIZE = 1e5;
char buff[BUFF_SIZE];
int buffPos = BUFF_SIZE-1;
void readChar()
{
if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
}
void readInt(int &num)
{
num = 0;
for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
{
num = 10*num + buff[buffPos]-'0';
}
}
void readLong(llong &num)
{
num = 0;
for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
{
num = 10*num + buff[buffPos]-'0';
}
}
int n, m, q;
struct SegmentTree
{
struct Node
{
llong minPrefix;
llong maxSuffix;
llong sumPositive;
llong sumNegative;
int minPrefixPos;
llong sum;
int c;
Node()
{
maxSuffix = minPrefix = minPrefixPos = sumPositive = sumNegative = sum = c = 0;
}
void assign(const Node &left, const Node &right)
{
sum = left.sum + right.sum;
sumPositive = left.sumPositive + right.sumPositive;
sumNegative = left.sumNegative + right.sumNegative;
minPrefix = std::min(left.minPrefix, left.sum + right.minPrefix);
if (minPrefix == left.minPrefix) minPrefixPos = left.minPrefixPos;
else minPrefixPos = right.minPrefixPos;
maxSuffix = std::max(right.maxSuffix, right.sum + left.maxSuffix);
c = std::max(left.c, right.c);
}
void operator += (const Node &right)
{
minPrefix = std::min(minPrefix, sum + right.minPrefix);
if (minPrefixPos == 0 || minPrefix == sum + right.minPrefix) minPrefixPos = right.minPrefixPos;
maxSuffix = std::max(right.maxSuffix, right.sum + maxSuffix);
sum = sum + right.sum;
sumPositive = sumPositive + right.sumPositive;
sumNegative = sumNegative + right.sumNegative;
c = std::max(c, right.c);
}
friend Node operator + (const Node &left, const Node &right)
{
Node result;
result.sum = left.sum + right.sum;
result.sumPositive = left.sumPositive + right.sumPositive;
result.sumNegative = left.sumNegative + right.sumNegative;
result.minPrefix = std::min(left.minPrefix, left.sum + right.minPrefix);
if (result.minPrefix == left.minPrefix) result.minPrefixPos = left.minPrefixPos;
else result.minPrefixPos = right.minPrefixPos;
result.maxSuffix = std::max(right.maxSuffix, right.sum + left.maxSuffix);
result.c = std::max(left.c, right.c);
return result;
}
};
Node tree[4*MAXN];
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].minPrefixPos = l;
return;
}
int mid = l + r >> 1;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node].assign(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, const int &queryPos, const int &queryVal, const int &queryC, const 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 = std::min(0LL, tree[node].sum);
tree[node].maxSuffix = std::max(0LL, tree[node].sum);
return;
}
int mid = l + r >> 1;
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].assign(tree[2*node], tree[2*node + 1]);
}
Node query(int l, int r, int node, const int &queryL, const int &queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
Node res;
int mid = l + r >> 1;
if (queryL <= mid) 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, const int &queryL, const int &queryR, const llong &k)
{
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 >> 1;
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 build()
{
build(1, q, 1);
}
void update(int pos, int val, int c, bool type)
{
update(1, q, 1, pos, val, c, type);
}
llong queryMaxSuffix(int l, int r)
{
return query(1, q, 1, l, r).maxSuffix;
}
llong queryMinPrefix(int l, int r)
{
return query(1, q, 1, l, r).minPrefix;
}
Node query(int l, int r)
{
return query(1, q, 1, l, r);
}
int queryMinPrefixPos(int l, int r)
{
return query(1, q, 1, l, r).minPrefixPos;
}
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()
{
tree.build();
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 r = tree.queryMinPrefixPos(1, time);
assert(r != time);
r += (tree.query(1, r).sum < 0);
if (r > time)
{
assert(r == time + 1);
answer[idx] = 0;
continue;
}
llong cntPositive = tree.query(r, time).sumPositive;
llong cntNegative = tree.query(r, time).sumNegative;
if (val + cntNegative > cntPositive) answer[idx] = 0;
else answer[idx] = tree.find(r, time, val + cntNegative);
}
}
}
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, val;
std::cin >> l >> r >> val;
activate[l].push_back({false, val, 0, i});
deactivate[r + 1].push_back({false, val, 0, i});
continue;
}
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 member function 'void SegmentTree::build(int, int, int)':
foodcourt.cpp:111:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In member function 'void SegmentTree::update(int, int, int, const int&, const int&, const int&, const bool&)':
foodcourt.cpp:139:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
139 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, const int&, const int&)':
foodcourt.cpp:153:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
153 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In member function 'llong SegmentTree::find(int, int, int, const int&, const int&, const llong&)':
foodcourt.cpp:176:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
176 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In function 'void readChar()':
foodcourt.cpp:20:38: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
16 ms |
73640 KB |
Output is correct |
| 3 |
Correct |
14 ms |
73564 KB |
Output is correct |
| 4 |
Correct |
15 ms |
73816 KB |
Output is correct |
| 5 |
Correct |
14 ms |
73820 KB |
Output is correct |
| 6 |
Runtime error |
73 ms |
149120 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
16 ms |
73640 KB |
Output is correct |
| 3 |
Correct |
14 ms |
73564 KB |
Output is correct |
| 4 |
Correct |
15 ms |
73816 KB |
Output is correct |
| 5 |
Correct |
14 ms |
73820 KB |
Output is correct |
| 6 |
Runtime error |
73 ms |
149120 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
162 ms |
155332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
518 ms |
171092 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
16 ms |
73640 KB |
Output is correct |
| 3 |
Correct |
14 ms |
73564 KB |
Output is correct |
| 4 |
Correct |
15 ms |
73816 KB |
Output is correct |
| 5 |
Correct |
14 ms |
73820 KB |
Output is correct |
| 6 |
Runtime error |
73 ms |
149120 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
142 ms |
154448 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
16 ms |
73640 KB |
Output is correct |
| 3 |
Correct |
14 ms |
73564 KB |
Output is correct |
| 4 |
Correct |
15 ms |
73816 KB |
Output is correct |
| 5 |
Correct |
14 ms |
73820 KB |
Output is correct |
| 6 |
Runtime error |
73 ms |
149120 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
16 ms |
73640 KB |
Output is correct |
| 3 |
Correct |
14 ms |
73564 KB |
Output is correct |
| 4 |
Correct |
15 ms |
73816 KB |
Output is correct |
| 5 |
Correct |
14 ms |
73820 KB |
Output is correct |
| 6 |
Runtime error |
73 ms |
149120 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
