//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);
}
};
const int N = 251'000;
int n, m, q, a, b, c, d, ile;
int zap[N]; // z jakiej grupy byli dodani ludzie w tym dodaniu;
long long p;
int main() {
scanf("%d%d%d", &n, &m, &q);
SegTreePlus off(n);
PerSegTreePlus customers(n);
for (int i = 1; i <= q; ++i) {
scanf("%d", &a);
if (a == 1) { // dodanie d ludzi na przedziale od a do b z grupy c
scanf("%d%d%d%d", &a, &b, &c, &d);
customers.Insert(ile, a, b, d);
++ile;
zap[ile] = c;
}
else if (a == 2) { // zabranie c ludzi z przedziału od a do b
scanf("%d%d%d", &a, &b, &c);
off.Insert(a, b, c);
}
else { // pytanie o a-tą pozycję i p-tą osobę
scanf("%d%lld", &a, &p);
p += off.Query(a);
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:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d%d%d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%d", &a);
| ~~~~~^~~~~~~~~~
foodcourt.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d%d%d%d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:120:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | scanf("%d%d%d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:124:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | scanf("%d%lld", &a, &p);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
9736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
300 ms |
70660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
34584 KB |
Output is correct |
| 2 |
Correct |
177 ms |
35956 KB |
Output is correct |
| 3 |
Correct |
173 ms |
35912 KB |
Output is correct |
| 4 |
Correct |
133 ms |
18680 KB |
Output is correct |
| 5 |
Correct |
167 ms |
35892 KB |
Output is correct |
| 6 |
Correct |
168 ms |
35908 KB |
Output is correct |
| 7 |
Correct |
28 ms |
2332 KB |
Output is correct |
| 8 |
Correct |
29 ms |
2656 KB |
Output is correct |
| 9 |
Correct |
83 ms |
19332 KB |
Output is correct |
| 10 |
Correct |
93 ms |
35760 KB |
Output is correct |
| 11 |
Correct |
123 ms |
35800 KB |
Output is correct |
| 12 |
Correct |
122 ms |
35740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
