//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
struct SegTreePlus {
int com;
vector <long long> st;
SegTreePlus(int n) {
com = 1;
while (com < n) {
com <<= 1;
}
st.resize(com << 1);
--com;
}
void Insert(int a, int b, int w) {
a += com;
b += com;
while (a <= b) {
if (a&1) {
st[a++] += w;
}
if (!(b&1)) {
st[b--] += w;
}
a >>= 1;
b >>= 1;
}
}
long long Query(int x) {
x += com;
long long ret = 0;
while (x) {
ret += st[x];
x >>= 1;
}
return ret;
}
};
struct SegTreeFind {
int com;
vector <long long> st;
SegTreeFind(int n) {
com = 1;
while (com < n) {
com <<= 1;
}
st.resize(com << 1);
--com;
}
void Insert(int x, int w) {
x += com;
st[x] = w;
x >>= 1;
while (x) {
st[x] = st[x * 2] + st[x * 2 + 1];
x >>= 1;
}
}
int SubFind(int x, int l, int r, long long w) {
if (l == r) {
return l;
}
if (st[x * 2] >= w) {
return SubFind(x * 2, l, (l + r) / 2, w);
}
return SubFind(x * 2 + 1, (l + r) / 2 + 1, r, w - st[x * 2]);
}
int Find(long long w) {
if (st[1] < w) {
return -1;
}
return SubFind(1, 1, com + 1, w);
}
};
struct SegTreeMerge {
struct node {
long long off, out;
};
int com;
vector <node> st;
SegTreeMerge(int n) {
com = 1;
while (com < n) {
com <<= 1;
}
st.resize(com << 1);
--com;
}
node merge(node p, node q) {
if (p.out >= q.off) {
return {p.off, p.out - q.off + q.out};
}
return {p.off + q.off - p.out, q.out};
}
void Insert(int x, int w) {
x += com;
if (w < 0) {
st[x] = {-w, 0};
}
else {
st[x] = {0, w};
}
x >>= 1;
while (x) {
st[x] = merge(st[x * 2], st[x * 2 + 1]);
x >>= 1;
}
}
long long Query(int a, int b) {
a += com;
b += com;
node ret = {0, 0};
vector <int> rg;
while (a <= b) {
if (a&1) {
ret = merge(ret, st[a]);
++a;
}
if (!(b&1)) {
rg.push_back(b);
--b;
}
a >>= 1;
b >>= 1;
}
reverse(rg.begin(), rg.end());
for (int i : rg) {
ret = merge(ret, st[i]);
}
return ret.off;
}
};
const int N = 251'000;
int n, m, q;
long long war[N];
long long wej[N][5];
vector <pair <int, int> > v[N], vv[N];
vector <int> que[N];
int odp[N];
int main() {
scanf("%d%d%d", &n, &m, &q);
SegTreePlus off(n);
for (int i = 1; i <= q; ++i) {
scanf("%lld", &wej[i][0]);
if (wej[i][0] == 1) { // dodanie d ludzi na przedziale od a do b z grupy c
scanf("%lld%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3], &wej[i][4]);
v[wej[i][1]].push_back({i, wej[i][4]});
v[wej[i][2] + 1].push_back({i, 0});
vv[wej[i][1]].push_back({i, wej[i][4]});
vv[wej[i][2] + 1].push_back({i, 0});
}
else if (wej[i][0] == 2) { // zabranie c ludzi z przedziału od a do b
scanf("%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3]);
v[wej[i][1]].push_back({i, -wej[i][3]});
v[wej[i][2] + 1].push_back({i, 0});
off.Insert(wej[i][1], wej[i][2], wej[i][3]);
}
else { // pytanie o a-tą pozycję i p-tą osobę
scanf("%lld%lld", &wej[i][1], &wej[i][2]);
que[wej[i][1]].push_back(i);
war[i] += wej[i][2] + off.Query(wej[i][1]);
}
}
SegTreeMerge eat(q);
for (int i = 1; i <= n; ++i) {
for (auto j : v[i]) {
eat.Insert(j.first, j.second);
}
for (int j : que[i]) {
war[j] -= eat.Query(1, j);
}
}
SegTreeFind customers(q);
for (int i = 1; i <= n; ++ i) {
for (auto j : vv[i]) {
customers.Insert(j.first, j.second);
}
for (int j : que[i]) {
odp[j] = customers.Find(war[j]);
}
}
for (int i = 1; i <= q; ++i) {
if (odp[i] == 0) {
continue;
}
if (odp[i] == -1) {
printf("0\n");
continue;
}
printf("%lld\n", wej[odp[i]][3]);
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | scanf("%d%d%d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%lld", &wej[i][0]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:169:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%lld%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3], &wej[i][4]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:176:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
176 | scanf("%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:182:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
182 | scanf("%lld%lld", &wej[i][1], &wej[i][2]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
18252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
18252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
28984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
403 ms |
58160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
18252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
28800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
18252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
18252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
