#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, R;
};
void del(SlideWindow &x, int K) {
if(x.L.empty() || x.L.back().first < K) {
if(!x.L.empty()) {
K -= x.L.back().first;
}
for(; !x.L.empty(); x.L.pop_back());
for(int cnt; !x.R.empty();) {
cnt = x.R.back().first - (x.R.size() == 1 ? 0ll : x.R[x.R.size() - 2].first);
x.L.push_back({(x.L.empty() ? 0ll : x.L.back().first) + cnt, x.R.back().second});
x.R.pop_back();
}
}
for(int cnt; K && !x.L.empty();) {
cnt = x.L.back().first - (x.L.size() == 1 ? 0ll : x.L[x.L.size() - 2].first);
if(K < cnt) {
x.L.back().first -= K;
K = 0;
} else {
K -= cnt;
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.empty() ? 0ll : x.R.back().first), C});
}
int get(SlideWindow &x, ll K) {
if((x.L.empty() ? 0ll : x.L.back().first) + (x.R.empty() ? 0ll : x.R.back().first) < K) {
return 0;
}
if(x.L.empty() || x.L.back().first < K) {
if(!x.L.empty()) {
K -= x.L.back().first;
}
int l = -1, r = x.R.size() - 1, m;
for(; l + 1 < r;) {
m = (l + r) / 2;
(x.R[m].first < K ? l : r) = m;
}
return x.R.empty() ? 0ll : 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.empty() ? 0ll : x.L[l].second;
}
const int N = 1<<18;
vector < SlideWindow > Shops;
vector < queue < pair < ll, int > > > tree;
void relax(int x, int i) {
for(; !tree[x].empty(); tree[x].pop()) {
add(Shops[i], tree[x].front().first, tree[x].front().second);
}
}
void Push(pair < int, int > tmp, int x) {
if(tree[x].empty() || tree[x].back().second != tmp.second) {
tree[x].push(tmp);
return;
}
tree[x].back().first += tmp.first;
}
void push(int x) {
int l = x * 2 + 1, r = x * 2 + 2;
for(; !tree[x].empty(); tree[x].pop()) {
Push(tree[x].front(), l);
Push(tree[x].front(), r);
}
}
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) {
Push(tmp, x);
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);
tree.resize(k << 1);
Shops.resize(m + 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:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
124 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
325480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
325480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
374 ms |
426480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
437 ms |
524288 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
325480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
477 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
325480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
325480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
