#include <bits/stdc++.h>
#define ll pair <long long, long long>
#define ii pair <int, int>
#define F first
#define S second
#define pb push_back
using namespace std;
const int N = 2e5 + 5e4 + 5;
int n, m, q, group[N], ans[N];
vector <ii> event[N], numadd[N], query[N];
long long cur[4 * N], Min[4 * N];
void update_cur(int s, int l, int r, int u, int val){
if (l == r){
cur[s] += val;
Min[s] = min(0ll, Min[s] + val);
return;
}
int mid = l + r >> 1;
if (mid >= u) update_cur(2 * s, l, mid, u, val);
else update_cur(2 * s + 1, mid + 1, r, u, val);
cur[s] = cur[2 * s] + cur[2 * s + 1];
Min[s] = min(Min[2 * s], cur[2 * s] + Min[2 * s + 1]);
}
ll get_cur(int s, int l, int r, int u){
if (l > u) return ll(0, 0);
if (r <= u) return ll(cur[s], Min[s]);
int mid = l + r >> 1;
ll A = get_cur(2 * s, l, mid, u);
ll B = get_cur(2 * s + 1, mid + 1, r, u);
return ll(A.F + B.F, min(A.S, A.F + B.S));
}
long long sumadd[4 * N];
void update_sumadd(int s, int l, int r, int u, int val){
if (l == r){
sumadd[s] += val;
return;
}
int mid = l + r >> 1;
if (mid >= u) update_sumadd(2 * s, l, mid, u, val);
else update_sumadd(2 * s + 1, mid + 1, r, u, val);
sumadd[s] = sumadd[2 * s] + sumadd[2 * s + 1];
}
long long get_sumadd(int s, int l, int r, int u){
if (l > u) return 0;
if (r <= u) return sumadd[s];
int mid = l + r >> 1;
return get_sumadd(2 * s, l, mid, u) + get_sumadd(2 * s + 1, mid + 1, r, u);
}
int get_pos(int s, int l, int r, long long val){
if (l == r) return l;
int mid = l + r >> 1;
if (sumadd[2 * s] < val) return get_pos(2 * s + 1, mid + 1, r, val - sumadd[2 * s]);
return get_pos(2 * s, l, mid, val);
}
void solve(){
cin >> n >> m >> q;
for (int i = 1; i <= q; ++ i){
ans[i] = -1;
int t; cin >> t;
if (t == 1){
int l, r, k; cin >> l >> r >> group[i] >> k;
event[l].pb(ii(i, k));
event[r + 1].pb(ii(i, -k));
numadd[l].pb(ii(i, k));
numadd[r + 1].pb(ii(i, -k));
}
if (t == 2){
int l, r, k; cin >> l >> r >> k;
event[l].pb(ii(i, -k));
event[r + 1].pb(ii(i, k));
}
if (t == 3){
int a, b; cin >> a >> b;
query[a].pb(ii(i, b));
}
}
for (int i = 1; i <= n; ++ i){
for (ii v : event[i]) update_cur(1, 1, q, v.F, v.S);
for (ii v : numadd[i]) update_sumadd(1, 1, q, v.F, v.S);
for (ii v : query[i]){
ll gnum_cur = get_cur(1, 1, q, v.F);
long long num_cur = gnum_cur.F - gnum_cur.S;
//cout << gnum_cur.F << ' ' << gnum_cur.S << endl;
long long num_add = get_sumadd(1, 1, q, v.F);
if (num_cur < v.S) ans[v.F] = 0;
else ans[v.F] = group[get_pos(1, 1, q, num_add - num_cur + v.S)];
}
}
for (int i = 1; i <= q; ++ i) if (ans[i] >= 0) cout << ans[i] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
foodcourt.cpp: In function 'void update_cur(int, int, int, int, int)':
foodcourt.cpp:24:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In function 'std::pair<long long int, long long int> get_cur(int, int, int, int)':
foodcourt.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In function 'void update_sumadd(int, int, int, int, int)':
foodcourt.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In function 'long long int get_sumadd(int, int, int, int)':
foodcourt.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = l + r >> 1;
| ~~^~~
foodcourt.cpp: In function 'int get_pos(int, int, int, long long int)':
foodcourt.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
31156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
30280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
24024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
21084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
