#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> II;
const int N = 2e5 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
/*
//subtask 3
struct F{
int L, R, sum;
F(int _L = 0, int _R = 0, int _sum = 0) : L(_L), R(_R), sum(_sum) {}
F operator + (const F& op) const{
return F(max(op.L, min(op.R, L + op.sum)),
max(op.L, min(op.R, R + op.sum)),
sum + op.sum);
}
};
int C;
struct ST_lazy{
int n;
vector<F> ST;
ST_lazy(int _n = 0){
n = _n;
ST.resize(4 * n + 5);
}
void down(int id, int l, int r){
if(l == r) return;
ST[id * 2] = ST[id * 2] + ST[id];
ST[id * 2 + 1] = ST[id * 2 + 1] + ST[id];
ST[id] = F(0, C, 0);
}
void update(int id, int l, int r, int u, int v, int add){
down(id, l, r);
if(r < u || v < l) return;
if(u <= l && r <= v){
ST[id] = ST[id] + F(0, C, add);
return;
}
int mid = l + r >> 1;
update(id * 2, l, mid, u, v, add);
update(id * 2 + 1, mid + 1, r, u, v, add);
}
int get(int id, int l, int r, int i){
down(id, l, r);
if(l == r) return max(ST[id].L, min(ST[id].R, ST[id].sum));
int mid = l + r >> 1;
if(i <= mid) return get(id * 2, l, mid, i);
return get(id * 2 + 1, mid + 1, r, i);
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
int n = c.size(), q = l.size();
ST_lazy ST(n);
C = c[0];
for(int i = 0; i < q; i ++){
ST.update(1, 1, n, l[i] + 1, r[i] + 1, v[i]);
}
vector<int> ans;
for(int i = 1; i <= n; i ++) ans.push_back(ST.get(1, 1, n, i));
return ans;
}
*/
/*
int n;
ll suf_min[N], suf_max[N], sum[N];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
n = v.size();
for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + v[i - 1];
suf_max[n] = suf_min[n] = sum[n];
for(int i = n - 1; i >= 0; i --){
suf_max[i] = max(suf_max[i + 1], sum[i]);
suf_min[i] = min(suf_min[i + 1], sum[i]);
}
vector<int> res;
for(int i = 0; i < (int)c.size(); i ++){
int pos = 0, l = 1, r = n;
while(l <= r){
int mid = l + r >> 1;
if(suf_max[mid] - suf_min[mid] > c[i]) pos = mid, l = mid + 1;
else r = mid - 1;
}
if(suf_max[pos] - sum[pos] > c[i]) res.push_back(c[i] - (suf_max[pos] - sum[n]));
else res.push_back(sum[n] - suf_min[pos]);
}
return res;
}
*/
// subtask 5
struct ST_lazy{
int n;
vector<ll> lazy, Min, Max;
ST_lazy(int _n = 0){
n = _n;
lazy.assign(4 * n + 5, 0);
Min.assign(4 * n + 5, 0);
Max.assign(4 * n + 5, 0);
}
void down(int id, int l, int r){
Min[id] += lazy[id], Max[id] += lazy[id];
if(l != r){
lazy[id * 2] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
}
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int add){
down(id, l, r);
if(r < u || v < l) return;
if(u <= l && r <= v){
Min[id] += add;
Max[id] += add;
if(l != r){
lazy[id * 2] += add;
lazy[id * 2 + 1] += add;
}
return;
}
int mid = l + r >> 1;
update(id * 2, l, mid, u, v, add);
update(id * 2 + 1, mid + 1, r, u, v, add);
Min[id] = min(Min[id * 2], Min[id * 2 + 1]);
Max[id] = max(Max[id * 2], Max[id * 2 + 1]);
}
II get(int id, int l, int r, int u, int v){
down(id, l, r);
if(r < u || v < l) return II(INF, -INF);
if(u <= l && r <= v) return II(Min[id], Max[id]);
int mid = l + r >> 1;
II L = get(id * 2, l, mid, u, v), R = get(id * 2 + 1, mid + 1, r, u, v);
return II(min(L.first, R.first), max(L.second, R.second));
}
int BS(int id, int l, int r, int c){
down(id, l, r);
if(l == r) return l;
int mid = l + r >> 1;
down(id * 2, l, mid);
down(id * 2 + 1, mid + 1, r);
if(Max[id * 2 + 1] - Min[id * 2 + 1] > c) return BS(id * 2 + 1, mid + 1, r, c);
return BS(id * 2, l, mid, c);
}
};
vector<II> qu[N];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
int n = c.size(), q = v.size();
for(int i = 0; i < q; i ++){
qu[l[i] + 1].push_back(II(i + 1, v[i]));
qu[r[i] + 2].push_back(II(i + 1, -v[i]));
}
ST_lazy ST(q + 1);
vector<int> ans;
for(int i = 1; i <= n; i ++){
int C = c[i - 1];
for(auto x : qu[i]) ST.update(1, 0, q, x.first, q, x.second);
int pos = ST.BS(1, 0, q, C);
II R = ST.get(1, 0, q, pos, q);
ll cur_v = ST.get(1, 0, q, pos, pos).first, last_v = ST.get(1, 0, q, q, q).first;
if(R.second - cur_v > C) ans.push_back(C - (R.second - last_v));
else ans.push_back(last_v - R.first);
}
return ans;
}
/*
int main(){
vector<int> res = distribute_candies({10, 15, 100}, {0, 0, 0}, {2, 2, 2}, {10, 6, -13});
for(int x : res) cout << x << " ";
}
*/
Compilation message
candies.cpp: In member function 'void ST_lazy::update(int, int, int, int, int, int)':
candies.cpp:126:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'II ST_lazy::get(int, int, int, int, int)':
candies.cpp:136:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
136 | int mid = l + r >> 1;
| ~~^~~
candies.cpp: In member function 'int ST_lazy::BS(int, int, int, int)':
candies.cpp:143:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
143 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4996 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5268 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
725 ms |
46428 KB |
Output is correct |
| 2 |
Correct |
717 ms |
45792 KB |
Output is correct |
| 3 |
Correct |
688 ms |
45516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
305 ms |
40380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4996 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5268 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
