//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 PerSegTreePlus {
struct node {
int l, r;
long long w;
};
int com;
vector <node> st;
vector <int> day;
PerSegTreePlus(int n) {
com = 1;
while (com < n) {
com <<= 1;
}
st.resize(1);
day.resize(1);
}
int SubInsert(int x, int l, int r, int ll, int rr, int w) {
if (r < ll || rr < l) {
return x;
}
if (ll <= l && r <= rr) {
st.push_back({st[x].l, st[x].r, st[x].w+w});
return st.size() - 1;
}
st.push_back(st[x]);
x = st.size() - 1;
int y = SubInsert(st[x].l, l, (l + r) / 2, ll, rr, w);
st[x].l = y;
y = SubInsert(st[x].r, (l + r) / 2 + 1, r, ll, rr, w);
st[x].r = y;
return x;
}
long long SubQuery(int x, int l, int r, int p) {
if (l == r) {
return st[x].w;
}
if (p <= (l + r) / 2) {
return st[x].w + SubQuery(st[x].l, l, (l + r) / 2, p);
}
return st[x].w + SubQuery(st[x].r, (l + r) / 2 + 1, r, p);
}
void Insert(int x, int l, int r, int w) {
day.push_back(SubInsert(day[x], 1, com, l, r, w));
}
long long Query(int x, int p) {
return SubQuery(day[x], 1, com, p);
}
};
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, a, b, c, d, ile;
long long war[N];
long long wej[N][5];
int zap[N]; // z jakiej grupy byli dodani ludzie w tym dodaniu;
vector <pair <int, int> > v[N];
vector <int> que[N];
int main() {
scanf("%d%d%d", &n, &m, &q);
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});
}
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});
}
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);
}
}
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);
}
}
SegTreePlus off(n);
PerSegTreePlus customers(n);
for (int i = 1; i <= q; ++i) {
if (wej[i][0] == 1) { // dodanie d ludzi na przedziale od a do b z grupy c
customers.Insert(ile, wej[i][1], wej[i][2], wej[i][4]);
++ile;
zap[ile] = wej[i][3];
}
else if (wej[i][0] == 2) { // zabranie c ludzi z przedziału od a do b
off.Insert(wej[i][1], wej[i][2], wej[i][3]);
}
else { // pytanie o a-tą pozycję i p-tą osobę
long long p = wej[i][2] + off.Query(a) - war[i];
a = wej[i][1];
if (customers.Query(ile, a) < p) { // nie ma tylu ludzi
printf("0\n");
continue;
}
int bp = 0, bk = ile, bs;
while (bk - bp > 1) {
bs = (bp + bk) / 2;
if (customers.Query(bs, a) < p) {
bp = bs;
}
else {
bk = bs;
}
}
printf("%d\n", zap[bk]);
}
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:176:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
176 | scanf("%d%d%d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%lld", &wej[i][0]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:180:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | scanf("%lld%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3], &wej[i][4]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:185:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | scanf("%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:190:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
190 | scanf("%lld%lld", &wej[i][1], &wej[i][2]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
29156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
778 ms |
109660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
53352 KB |
Output is correct |
| 2 |
Correct |
196 ms |
53964 KB |
Output is correct |
| 3 |
Correct |
237 ms |
54164 KB |
Output is correct |
| 4 |
Correct |
125 ms |
36028 KB |
Output is correct |
| 5 |
Correct |
197 ms |
53508 KB |
Output is correct |
| 6 |
Correct |
215 ms |
54132 KB |
Output is correct |
| 7 |
Correct |
49 ms |
18856 KB |
Output is correct |
| 8 |
Correct |
43 ms |
19248 KB |
Output is correct |
| 9 |
Correct |
102 ms |
36840 KB |
Output is correct |
| 10 |
Correct |
123 ms |
52144 KB |
Output is correct |
| 11 |
Correct |
169 ms |
53520 KB |
Output is correct |
| 12 |
Correct |
151 ms |
53480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
