#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct seg{
int sz = 1; vector<ll>mn,mx,sum,op,add;
seg(int n){
while(sz < n) sz*=2;
mn.assign(sz*2,0ll);
mx.assign(sz*2,0ll);
op.assign(sz*2,0ll);
sum.assign(sz*2,0ll);
add.assign(sz*2,0ll);
}
void push(int x,int lx,int rx){
if(rx-lx == 1) return;
int m = (lx+rx)/2;
add[x*2+1] += add[x];
add[x*2+2] += add[x];
sum[x*2+1] += add[x] * (m-lx);
sum[x*2+2] += add[x] * (rx-m);
sum[x] = sum[x*2+1] + sum[x*2+2];
add[x] = 0;
}
void update(int l,int r,ll v,int x=0,int lx=0,int rx=-1){
if(rx == -1){r++;rx=sz;}
push(x,lx,rx);
if(rx <= l || lx >= r) return;
if(rx <= r && lx >= l){
op[x] += v;
mn[x] += v;
mx[x] += v;
add[x] += v;
sum[x] += (rx-lx)*v;
return;
}
int m = (lx+rx)/2;
update(l,r,v,x*2+1,lx,m);
update(l,r,v,x*2+2,m,rx);
mn[x] = min(mn[x*2+1] , mn[x*2+2]) + op[x];
mx[x] = max(mx[x*2+1] , mx[x*2+2]) + op[x];
sum[x] = sum[x*2+1] + sum[x*2+2];}
ll getMIN(int l,int r,int x=0,int lx=0,int rx=-1){
if(rx == -1){rx=sz;r++;}
if(rx <= l || lx >= r) return 1e15;
if(rx <= r && lx >= l) return mn[x];
int m = (lx+rx)/2;
return min(getMIN(l,r,x*2+1,lx,m),getMIN(l,r,x*2+2,m,rx)) + op[x];}
ll getMAX(int l,int r,int x=0,int lx=0,int rx=-1){
if(rx == -1){rx=sz;r++;}
if(rx <= l || lx >= r) return -1e15;
if(rx <= r && lx >= l) return mx[x];
int m = (lx+rx)/2;
return max(getMAX(l,r,x*2+1,lx,m),getMAX(l,r,x*2+2,m,rx)) + op[x];}
ll getSUM(int l,int r,int x=0,int lx=0,int rx=-1){
if(rx == -1){rx=sz;r++;}
push(x,lx,rx);
if(rx <= l || lx >= r) return 0ll;
if(rx <= r && lx >= l) return sum[x];
int m = (lx+rx)/2;
return getSUM(l,r,x*2+1,lx,m)+getSUM(l,r,x*2+2,m,rx);}};
int n, m;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
n = c.size();
m = r.size();
vector<int> s(n);
vector<vector<int>> L(n),R(n);
for(int i=0; i < m;i++){
L[l[i]].push_back(i);
R[r[i]].push_back(i);
}
seg st(m + 2);
for(int i=0; i < n;i++){
for(int x : L[i]) st.update(x + 2, m + 1, v[x]);
int l = 0;
int r = m;
int id = -1;
ll cmx, cmn;
while(l <= r){
int mid = (l+r)/2;
ll a,b;
a = st.getMAX(mid + 1, m + 1), b = st.getMIN(mid + 1, m + 1);
if(a - b >= c[i]){
l = mid+1;
id = mid;
cmx = a;
cmn = b;
} else r = mid-1;
}
// cout << cmx << ' ' << cmn << endl;
if(id == -1){
// l = 0;
// r = m;
// int limit = st.getMIN()
// while(l <= r){
// int mid = (l + r)/2;
// if(st.getMIN())
// }
s[i] = st.getSUM(m+1,m+1) - cmn;
continue;
}
int cond = 0;
ll curr;
id++;
if(cmx == st.getMAX(id + 1, m + 1)) cond = 1, curr = cmx;
else cond = 0, curr = cmn;
if(cond){
int l = id - 1;
int r = m;
while(l <= r){
int mid = (l+r)/2;
if(st.getMAX(mid + 1, m + 1) == curr){
id = mid;
l = mid + 1;
} else r = mid - 1;
}
id++;
// cout << st.getSUM(id + 1, m + 1) << ' ' << id << ' ';
s[i] = c[i] - (st.getSUM(id, id) - st.getSUM(m+1,m+1));
} else{
int l = id - 1;
int r = m;
while(l <= r){
int mid = (l+r)/2;
if(st.getMIN(mid + 1, m + 1) == curr){
id = mid;
l = mid + 1;
} else r = mid - 1;
}
id++;
s[i] = st.getSUM(m+1,m+1) - st.getSUM(id, id);
}
for(int x : R[i]) st.update(x + 2, m + 1, -v[x]);
}
return s;
}
// void solve(){
// cin >> n;
// vector<int> c(n);
// for(int i=0; i < n;i++) cin >> c[i];
// int q; cin >> q;
// vector<int> l(q),r(q),v(q);
// for(int i=0; i < q;i++) cin >> l[i];
// for(int i=0; i < q;i++) cin >> r[i];
// for(int i=0; i < q;i++) cin >> v[i];
// vector<int> ans = distribute_candies(c,l,r,v); cout << endl;
// for(int x : ans) cout << x << ' '; cout << endl;
// }
// int32_t main(){
// ios::sync_with_stdio(false);
// cin.tie();
// cout.tie();
// int t=1;
// // cin >> t;
// while(t--){
// // cout << t << ":\n";
// solve();
// }
// }
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:112:39: warning: 'cmn' may be used uninitialized in this function [-Wmaybe-uninitialized]
112 | s[i] = st.getSUM(m+1,m+1) - cmn;
| ~~~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1944 ms |
48440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
