#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;
llong sum;
int c;
Node()
{
maxSuffix = minPrefix = 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);
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);
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);
}
};
Node tree[4*MAXN];
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 += query(mid + 1, r, 2*node + 1, queryL, queryR);
return res;
}
std::pair <llong,llong> queryMaxSuffix(int l, int r, int node, const int &queryL, const int &queryR)
{
if (queryL <= l && r <= queryR)
{
return {tree[node].maxSuffix, tree[node].sum};
}
int mid = l + r >> 1;
llong left = 0, sL = 0, right = 0, sR = 0;
if (queryL <= mid)
{
auto p = queryMaxSuffix(l, mid, 2*node, queryL, queryR);
left = p.first; sL = p.second;
}
if (mid + 1 <= queryR)
{
auto p = queryMaxSuffix(mid + 1, r, 2*node + 1, queryL, queryR);
right = p.first; sR = p.second;
}
return {std::max(right, sR + left), sL + sR};
}
std::pair <llong,llong> queryMinPrefix(int l, int r, int node, const int &queryL, const int &queryR)
{
if (queryL <= l && r <= queryR)
{
return {tree[node].minPrefix, tree[node].sum};
}
int mid = l + r >> 1;
llong left = 0, sL = 0, right = 0, sR = 0;
if (queryL <= mid)
{
auto p = queryMinPrefix(l, mid, 2*node, queryL, queryR);
left = p.first; sL = p.second;
}
if (mid + 1 <= queryR)
{
auto p = queryMinPrefix(mid + 1, r, 2*node + 1, queryL, queryR);
right = p.first; sR = p.second;
}
return {std::max(left, sL + right), sL + sR};
}
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 update(int pos, int val, int c, bool type)
{
update(1, q, 1, pos, val, c, type);
}
llong queryMaxSuffix(int l, int r)
{
return queryMaxSuffix(1, q, 1, l, r).first;
}
llong queryMinPrefix(int l, int r)
{
return queryMinPrefix(1, q, 1, l, r).first;
}
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 >> 1;
llong res = tree.queryMinPrefix(mid, time);
if (mid > 1) res += tree.queryMaxSuffix(1, mid - 1);
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;
if (val + cntNegative > cntPositive) answer[idx] = 0;
else answer[idx] = tree.find(r, time, val + cntNegative);
}
}
}
void input()
{
readInt(n);
readInt(m);
readInt(q);
for (int i = 1 ; i <= q ; ++i)
{
int qType;
readInt(qType);
if (qType == 1)
{
int l, r, c, val;
readInt(l);
readInt(r);
readInt(c);
readInt(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;
readInt(l);
readInt(r);
readInt(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;
readInt(pos);
readLong(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::update(int, int, int, const int&, const int&, const int&, const bool&)':
foodcourt.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, const int&, const int&)':
foodcourt.cpp:119:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
119 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In member function 'std::pair<long long int, long long int> SegmentTree::queryMaxSuffix(int, int, int, const int&, const int&)':
foodcourt.cpp:132:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
132 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In member function 'std::pair<long long int, long long int> SegmentTree::queryMinPrefix(int, int, int, const int&, const int&)':
foodcourt.cpp:156:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
156 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In member function 'llong SegmentTree::find(int, int, int, const int&, const int&, const llong&)':
foodcourt.cpp:190:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
190 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:265:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
265 | 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 |
Incorrect |
16 ms |
65880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
65880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
69088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
713 ms |
76788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
65880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
68580 KB |
Output is correct |
| 2 |
Correct |
189 ms |
68836 KB |
Output is correct |
| 3 |
Correct |
172 ms |
68900 KB |
Output is correct |
| 4 |
Correct |
117 ms |
68028 KB |
Output is correct |
| 5 |
Correct |
170 ms |
68472 KB |
Output is correct |
| 6 |
Correct |
179 ms |
68948 KB |
Output is correct |
| 7 |
Correct |
100 ms |
68012 KB |
Output is correct |
| 8 |
Correct |
108 ms |
67728 KB |
Output is correct |
| 9 |
Correct |
144 ms |
68296 KB |
Output is correct |
| 10 |
Correct |
113 ms |
67932 KB |
Output is correct |
| 11 |
Correct |
170 ms |
68496 KB |
Output is correct |
| 12 |
Correct |
159 ms |
68688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
65880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
65880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
