#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef deque < pair < short int, short int > > QQ;
void del(QQ &L, QQ &R, int K) {
if(L.empty() || L.back().first < K) {
if(!L.empty()) {
K -= L.back().first;
}
for(; !L.empty(); L.pop_back());
for(int cnt; !R.empty();) {
cnt = R.back().first - (R.size() == 1 ? 0ll : R[R.size() - 2].first);
L.push_back({(L.empty() ? 0ll : L.back().first) + cnt, R.back().second});
R.pop_back();
}
}
for(int cnt; K && !L.empty();) {
cnt = L.back().first - (L.size() == 1 ? 0ll : L[L.size() - 2].first);
if(K < cnt) {
L.back().first -= K;
K = 0;
} else {
K -= cnt;
L.pop_back();
}
}
}
void add(QQ &L, QQ &R, ll K, int C) {
if(!C) {
del(L, R, K);
return;
}
R.push_back({K + (R.empty() ? 0ll : R.back().first), C});
}
int get(QQ &L, QQ &R, ll K) {
if((L.empty() ? 0ll : L.back().first) + (R.empty() ? 0ll : R.back().first) < K) {
return 0;
}
if(L.empty() || L.back().first < K) {
if(!L.empty()) {
K -= L.back().first;
}
int l = -1, r = R.size() - 1, m;
for(; l + 1 < r;) {
m = (l + r) / 2;
(R[m].first < K ? l : r) = m;
}
return R.empty() ? 0ll : R[r].second;
}
int l = 0, r = L.size(), m;
for(; l + 1 < r;) {
m = (l + r) / 2;
(L[m].first < K ? r : l) = m;
}
return L.empty() ? 0ll : L[l].second;
}
vector < QQ > ShopsL, ShopsR;
vector < queue < pair < short int, short int > > > tree;
void relax(int x, int i) {
for(; !tree[x].empty(); tree[x].pop()) {
add(ShopsL[i], ShopsR[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(ShopsL[lx], ShopsR[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);
ShopsL.resize(m + 1);
ShopsR.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:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
119 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
322460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
322460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
295 ms |
425200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
482 ms |
524288 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
322460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
499632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
322460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
322460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
