#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct SlideWindow{
deque < pair < ll, int > > L = {{0, 0}}, R = {{0, 0}}, S;
deque < int > cnt;
};
void del(SlideWindow &x, int K) {
if(x.L.back().first < K) {
K -= x.L.back().first;
for(; x.L.back().first; x.L.pop_back(), x.cnt.pop_back());
for(; x.R.back().first;) {
x.cnt.push_back(x.S.back().first);
x.L.push_back({x.L.back().first + x.cnt.back(), x.S.back().second});
x.S.pop_back();
x.R.pop_back();
}
}
for(; K && x.L.back().first;) {
if(K < x.cnt.back()) {
x.L.back().first -= K;
x.cnt.back() -= K;
K = 0;
} else {
K -= x.cnt.back();
x.cnt.pop_back();
x.L.pop_back();
}
}
}
void add(SlideWindow &x, ll K, int C) {
if(!C) {
del(x, K);
return;
}
x.R.push_back({K + x.R.back().first, C});
x.S.push_back({K, C});
}
int get(SlideWindow &x, ll K) {
if(x.L.back().first + x.R.back().first < K) {
return 0;
}
if(x.L.back().first < K) {
K -= x.L.back().first;
int l = 0, r = x.R.size(), m;
for(; l + 1 < r;) {
m = (l + r) / 2;
(x.R[m].first < K ? l : r) = m;
}
return x.R[r].second;
}
int l = 0, r = x.L.size(), m;
for(; l + 1 < r;) {
m = (l + r) / 2;
(x.L[m].first < K ? r : l) = m;
}
return x.L[l].second;
}
struct node{
queue < pair < ll, int > > q;
};
const int N = 1<<18;
SlideWindow Shops[N];
node tree[N<<1];
void relax(int x, int i) {
for(; !tree[x].q.empty(); tree[x].q.pop()) {
add(Shops[i], tree[x].q.front().first, tree[x].q.front().second);
}
}
void push(int x) {
int l = x * 2 + 1, r = x * 2 + 2;
for(; !tree[x].q.empty(); tree[x].q.pop()) {
tree[l].q.push(tree[x].q.front());
tree[r].q.push(tree[x].q.front());
}
}
void add_to_que(int &l, int &r, pair < int, int > &tmp, int x, int lx, int rx) {
if(r <= lx || rx <= l) {
return;
}
if(l <= lx && rx <= r) {
tree[x].q.push(tmp);
return;
}
push(x);
int m = (lx + rx) / 2;
add_to_que(l, r, tmp, x * 2 + 1, lx, m);
add_to_que(l, r, tmp, x * 2 + 2, m, rx);
}
int get(int &pos, ll &K, int x, int lx, int rx) {
if(lx + 1 == rx) {
relax(x, lx);
return get(Shops[lx], K);
}
push(x);
int m = (lx + rx) / 2;
return pos < m ?
get(pos, K, x * 2 + 1, lx, m) :
get(pos, K, x * 2 + 2, m, rx) ;
}
main() {
#ifdef Home
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Home
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q, k = 1;
pair < int, int > tmp;
ll T;
for(cin >> n >> m >> q; k <= n; k <<= 1);
for(int t, L, R, C, K; q --> 0;) {
cin >> t;
if(t == 1) {
cin >> L >> R >> C >> K;
tmp = {K, C};
++ R;
add_to_que(L, R, tmp, 0, 0, k);
} else if(t == 2) {
cin >> L >> R >> K;
++ R;
tmp = {K, 0};
add_to_que(L, R, tmp, 0, 0, k);
} else {
cin >> C >> T;
cout << get(C, T, 0, 0, k) << '\n';
}
}
}
Compilation message
foodcourt.cpp:120:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
120 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
212 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
212 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
185 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
183 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
212 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
185 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
212 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
212 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
