#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,ll> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 250005;
struct IT {
vector<ll> lo, hi, lazy;
IT (int sz) : lo(4 * sz), hi(4 * sz), lazy(4 * sz) {}
void apply (int k, ll val) {
lo[k] += val, hi[k] += val, lazy[k] += val;
}
void pushDown (int k) {
if (!lazy[k]) return;
apply(2 * k, lazy[k]), apply(2 * k + 1, lazy[k]), lazy[k] = 0;
}
void update (int a, int b, ll val, int k, int l, int r) {
if (b < l || r < a) return;
if (a <= l && r <= b)
return apply(k, val), void();
pushDown(k);
int mid = (l + r) >> 1;
update(a, b, val, 2 * k, l, mid);
update(a, b, val, 2 * k + 1, mid + 1, r);
lo[k] = min(lo[2 * k], lo[2 * k + 1]);
hi[k] = max(hi[2 * k], hi[2 * k + 1]);
}
void walk (ll cur, int k, int l, int r, vector<tt> &vec) {
if (lo[k] >= cur || hi[k] == 0) return;
if (l == r)
return vec.emplace_back(l, r, lo[k]), void();
pushDown(k);
int mid = (l + r) >> 1;
walk(cur, 2 * k, l, mid, vec);
walk(cur, 2 * k + 1, mid + 1, r, vec);
}
void breakDown (int a, int b, ll cur, int k, int l, int r, vector<tt> &vec) {
if (b < l || r < a) return;
if (lo[k] >= cur || hi[k] == 0) return;
if (a <= l && r <= b)
return walk(cur, k, l, r, vec), void();
pushDown(k);
int mid = (l + r) >> 1;
breakDown(a, b, cur, 2 * k, l, mid, vec);
breakDown(a, b, cur, 2 * k + 1, mid + 1, r, vec);
}
} tree(mn);
struct BIT {
vector<ll> tr;
BIT (int sz) : tr(sz + 1) {}
int p (int k) { return k & -k; }
void update (int pos, int val) {
for (; pos < tr.size(); pos += p(pos)) tr[pos] += val;
}
ll preSum (int pos) {
ll ans = 0;
for (; pos; pos -= p(pos)) ans += tr[pos];
return ans;
}
int walk (ll ub) {
int ans = 0, lg = 31 - __builtin_clz(tr.size());
ll sum = 0;
for (int msk = (1 << lg); msk > 0; msk >>= 1) {
if ((ans | msk) < tr.size() && tr[ans | msk] + sum < ub) ans |= msk, sum += tr[ans];
}
return ans;
}
} customer(mn), cut(mn);
vector<pl> openCust[mn], openCut[mn], closeCust[mn], closeCut[mn], query[mn];
int group[mn], ans[mn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q; cin >> n >> m >> q;
for (int i = 1; i <= q; i++) {
int type; cin >> type;
if (type == 1) {
int l, r; ll ppl; cin >> l >> r >> group[i] >> ppl;
openCust[l].emplace_back(i, ppl);
closeCust[r].emplace_back(i, ppl);
tree.update(l, r, ppl, 1, 1, n);
}
else if (type == 2) {
int l, r; ll cut; cin >> l >> r >> cut;
vector<tt> updates;
tree.breakDown(l, r, cut, 1, 1, n, updates);
int sz = updates.size();
for (int i = 0; i < sz; i++) {
int curL, curR; ll w; tie(curL, curR, w) = updates[i];
if (l < curL) updates.emplace_back(l, curL - 1, cut);
l = curR + 1;
}
if (l <= r) updates.emplace_back(l, r, cut);
for (auto [l, r, w] : updates) {
openCut[l].emplace_back(i, w);
closeCut[r].emplace_back(i, w);
tree.update(l, r, -w, 1, 1, n);
}
}
else {
int pos; ll ppl; cin >> pos >> ppl;
query[pos].emplace_back(i, ppl);
}
ans[i] = -1;
}
for (int i = 1; i <= n; i++) {
for (auto [crew, sz] : openCust[i])
customer.update(crew, sz);
for (auto [crew, sz] : openCut[i])
cut.update(crew, sz);
for (auto [moment, ppl] : query[i]) {
ll curCustomer = customer.preSum(moment), leftCustomer = cut.preSum(moment);
if (curCustomer - leftCustomer < ppl) ans[moment] = 0;
else {
int crew = customer.walk(leftCustomer + ppl) + 1;
ans[moment] = group[crew];
}
}
for (auto [crew, sz] : closeCust[i])
customer.update(crew, -sz);
for (auto [crew, sz] : closeCut[i])
cut.update(crew, -sz);
}
for (int i = 1; i <= q; i++)
if (ans[i] != -1) cout << ans[i] << "\n";
return 0;
}
Compilation message
foodcourt.cpp: In member function 'void BIT::update(int, int)':
foodcourt.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (; pos < tr.size(); pos += p(pos)) tr[pos] += val;
| ~~~~^~~~~~~~~~~
foodcourt.cpp: In member function 'int BIT::walk(ll)':
foodcourt.cpp:82:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if ((ans | msk) < tr.size() && tr[ans | msk] + sum < ub) ans |= msk, sum += tr[ans];
| ~~~~~~~~~~~~^~~~~~~~~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:118:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
118 | for (auto [l, r, w] : updates) {
| ^
foodcourt.cpp:132:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
132 | for (auto [crew, sz] : openCust[i])
| ^
foodcourt.cpp:134:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
134 | for (auto [crew, sz] : openCut[i])
| ^
foodcourt.cpp:137:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
137 | for (auto [moment, ppl] : query[i]) {
| ^
foodcourt.cpp:146:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
146 | for (auto [crew, sz] : closeCust[i])
| ^
foodcourt.cpp:148:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
148 | for (auto [crew, sz] : closeCut[i])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
57424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
57424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1051 ms |
233064 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1037 ms |
231136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
57424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
60292 KB |
Output is correct |
| 2 |
Correct |
77 ms |
60500 KB |
Output is correct |
| 3 |
Correct |
90 ms |
60444 KB |
Output is correct |
| 4 |
Correct |
68 ms |
59472 KB |
Output is correct |
| 5 |
Correct |
70 ms |
60052 KB |
Output is correct |
| 6 |
Correct |
79 ms |
60500 KB |
Output is correct |
| 7 |
Correct |
43 ms |
59584 KB |
Output is correct |
| 8 |
Correct |
42 ms |
59328 KB |
Output is correct |
| 9 |
Correct |
50 ms |
59852 KB |
Output is correct |
| 10 |
Correct |
55 ms |
59348 KB |
Output is correct |
| 11 |
Correct |
70 ms |
60044 KB |
Output is correct |
| 12 |
Correct |
75 ms |
60108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
57424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
57424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
