#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 < ll, int > > QQ;
map < int, QQ > ShopsL, ShopsR;
void del(int i, int K) {
if(ShopsL[i].empty() || ShopsL[i].back().first < K) {
if(!ShopsL[i].empty()) {
K -= ShopsL[i].back().first;
}
for(; !ShopsL[i].empty(); ShopsL[i].pop_back());
for(int cnt; !ShopsR[i].empty();) {
cnt = ShopsR[i].back().first - (ShopsR[i].size() == 1 ? 0ll : ShopsR[i][ShopsR[i].size() - 2].first);
ShopsL[i].push_back({(ShopsL[i].empty() ? 0ll : ShopsL[i].back().first) + cnt, ShopsR[i].back().second});
ShopsR[i].pop_back();
}
}
for(int cnt; K && !ShopsL[i].empty();) {
cnt = ShopsL[i].back().first - (ShopsL[i].size() == 1 ? 0ll : ShopsL[i][ShopsL[i].size() - 2].first);
if(K < cnt) {
ShopsL[i].back().first -= K;
K = 0;
} else {
K -= cnt;
ShopsL[i].pop_back();
}
}
}
void add(int i, ll K, int C) {
if(!C) {
del(i, K);
return;
}
ShopsR[i].push_back({K + (ShopsR[i].empty() ? 0ll : ShopsR[i].back().first), C});
}
int Get(int i, ll K) {
if((ShopsL[i].empty() ? 0ll : ShopsL[i].back().first) + (ShopsR[i].empty() ? 0ll : ShopsR[i].back().first) < K) {
return 0;
}
if(ShopsL[i].empty() || ShopsL[i].back().first < K) {
if(!ShopsL[i].empty()) {
K -= ShopsL[i].back().first;
}
int l = -1, r = ShopsR[i].size() - 1, m;
for(; l + 1 < r;) {
m = (l + r) / 2;
(ShopsR[i][m].first < K ? l : r) = m;
}
return ShopsR[i].empty() ? 0ll : ShopsR[i][r].second;
}
int l = 0, r = ShopsL[i].size(), m;
for(; l + 1 < r;) {
m = (l + r) / 2;
(ShopsL[i][m].first < K ? r : l) = m;
}
return ShopsL[i].empty() ? 0ll : ShopsL[i][l].second;
}
struct node{
node *left = NULL, *right = NULL;
int l, r;
queue < pair < ll, int > > q;
node(int l, int r) :l(l),r(r){};
};
void relax(node *x, int i) {
for(; !x->q.empty(); x->q.pop()) {
add(i, x->q.front().first, x->q.front().second);
}
}
void Push(pair < int, int > tmp, node *x) {
if(x->q.empty() || x->q.back().second != tmp.second) {
x->q.push(tmp);
return;
}
x->q.back().first += tmp.first;
}
void push(node *x) {
if(x->left == NULL) {
x->left = new node(x->l, (x->r + x->l) / 2);
}
if(x->right == NULL) {
x->right = new node((x->l + x->r) / 2, x->r);
}
for(; !x->q.empty(); x->q.pop()) {
Push(x->q.front(), x->left);
Push(x->q.front(), x->right);
}
}
void add_to_que(int l, int r, pair < int, int > tmp, node *x) {
if(r <= x->l || x->r <= l) {
return;
}
if(l <= x->l && x->r <= r) {
Push(tmp, x);
return;
}
push(x);
add_to_que(l, r, tmp, x->left);
add_to_que(l, r, tmp, x->right);
}
int get(int pos, ll K, node *x) {
if(x->l + 1 == x->r) {
relax(x, x->l);
return Get(x->l, K);
}
push(x);
return pos < x->left->r ?
get(pos, K, x->left) :
get(pos, K, x->right) ;
}
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);
node *tree = new node(0, k);
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, tree);
} else if(t == 2) {
cin >> L >> R >> K;
++ R;
tmp = {K, 0};
add_to_que(L, R, tmp, tree);
} else {
cin >> C >> T;
cout << get(C, T, tree) << '\n';
}
}
}
Compilation message
foodcourt.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
128 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
6208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
6208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
112204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1006 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
6208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
910 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
6208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
6208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
