#include <bits/stdc++.h>
//#include "candies.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1 << 18;
ll n, q, lazy[b * 2];
vector<pair<int, int>> tmp[b];
pair<ll, ll> seg[b * 2];
void upd_lazy(int ix, int l, int r){
if(!lazy[ix]) return;
seg[ix].first += lazy[ix];
seg[ix].second += lazy[ix];
if(l ^ r){
lazy[ix * 2] += lazy[ix];
lazy[ix * 2 + 1] += lazy[ix];
}
lazy[ix] = 0;
return;
}
void upd(int ix, int nl, int nr, int l, int r, ll v){
upd_lazy(ix, nl, nr);
if(nl > r || nr < l) return;
if(nl >= l && nr <= r){
lazy[ix] += v;
upd_lazy(ix, nl, nr);
return;
}
int m = (nl + nr) / 2;
upd(ix * 2, nl, m, l, r, v);
upd(ix * 2 + 1, m + 1, nr, l, r, v);
seg[ix].first = min(seg[ix * 2].first, seg[ix * 2 + 1].first);
seg[ix].second = max(seg[ix * 2].second, seg[ix * 2 + 1].second);
return;
}
ll f(int k){
int ix = 1, l = 0, r = b - 1, m;
while(l < r){
upd_lazy(1, l, r);
m = (l + r) / 2;
ix <<= 1;
if(k <= m) r = m;
else l = m + 1, ix++;
}
return seg[ix].first;
}
int find(ll c){
ll ix = 1, l = 0, r = b - 1, mx = -1e18, mn = 1e18;
upd_lazy(ix, l, r);
while(l < r){
int mid = (l + r) / 2;
ix = ix * 2 + 1;
upd_lazy(ix, mid + 1, r);
ll mnn = min(mn, seg[ix].first);
ll mxx = max(mx, seg[ix].second);
if(mxx - mnn > c) l = mid + 1;
else{
ix--;
upd_lazy(ix, l, mid);
r = mid;
mn = min(mn, mnn);
mx = max(mx, mxx);
}
}
ll s = f(l + 1);
ll e = f(q);
//cout << l + 1 << ' ' << q << ' ' << s << ' ' << e << '\n';
if(f(l) >= s) return max(e - s, 0LL);
return min(c - s + e, c);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
vector<int> ans(n);
q = l.size();
for(int i = 0; i < q; i++){
tmp[l[i]].emplace_back(i + 1, v[i]);
tmp[r[i] + 1].emplace_back(i + 1, -v[i]);
}
for(int i = 0; i <= q; i++) seg[b + i] = {0, 0};
for(int i = q + 1; i < b; i++) seg[b + i] = {1e18, -1e18};
for(int i = b - 1; i; i--)
seg[i] = {min(seg[i * 2].first, seg[i * 2 + 1].first), max(seg[i * 2].second, seg[i * 2 + 1].second)};
for(int i = 0; i < n; i++){
//cout << "now is " << i << '\n';
for(auto& [qi, x] : tmp[i]) upd(1, 0, b - 1, qi, q, x);//, cout << "upd " << qi << ' ' << q << ' ' << x << '\n';
//for(int i = 0; i <= q; i++) cout << f(i) << ' ';
//cout << '\n';
auto[mn, mx] = seg[1];
if(mx - mn <= c[i]) ans[i] = mx - mn;
else ans[i] = find(c[i]);
}
return ans;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector<int> c, l, r, v;
int n, q, x;
cin >> n;
for(int i = 0; i < n; i++) cin >> x, c.emplace_back(x);
cin >> q;
for(int i = 0; i < q; i++){
cin >> x, l.emplace_back(x);
cin >> x, r.emplace_back(x);
cin >> x, v.emplace_back(x);
}
vector<int> ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; i++) cout << ans[i] << ' ';
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14676 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
14664 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
549 ms |
31908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14676 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
14664 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
