#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
const int MAXN = 2e5+5;
ll mnn[4*MAXN],mxx[4*MAXN],lazy[4*MAXN],ans[MAXN],C[MAXN];
int n,q;
void upd(int v,int l,int r,int tl,int tr,ll val){
if(l==tl && r==tr){
lazy[v]+=val;
mnn[v]+=val;
mxx[v]+=val;
return;
}
int tm = (tl+tr)/2;
if(r<=tm)upd(2*v,l,r,tl,tm,val);
else if(l>tm)upd(2*v+1,l,r,tm+1,tr,val);
else{
upd(2*v,l,tm,tl,tm,val);
upd(2*v+1,tm+1,r,tm+1,tr,val);
}
mnn[v] = min(mnn[2*v],mnn[2*v+1])+lazy[v];
mxx[v] = max(mxx[2*v],mxx[2*v+1])+lazy[v];
}
ll mnquery(int v,int l,int r,int tl,int tr){
if(l>r)return 1e18;
if(l==tl && r==tr)return mnn[v];
int tm = (tl+tr)/2;
return min(mnquery(2*v,l,min(r,tm),tl,tm),
mnquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v];
}
ll mxquery(int v,int l,int r,int tl,int tr){
if(l>r)return 0;
if(l==tl && r==tr)return mxx[v];
int tm = (tl+tr)/2;
return max(mxquery(2*v,l,min(r,tm),tl,tm),
mxquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v];
}
vector<pair<int,int>>ch[4*MAXN];
void add(int v,int l,int r,int tl,int tr,int t,ll val){
if(l>r)return;
if(l==tl && r==tr){
ch[v].pb({t+1,val});
return;
}
int tm = (tl+tr)/2;
add(2*v,l,min(r,tm),tl,tm,t,val);
add(2*v+1,max(tm+1,l),r,tm+1,tr,t,val);
}
set<pair<int,int>>cur;
ll cursum = 0;
void solve(int v,int tl,int tr){
for(auto x:ch[v]){
upd(1,x.fi,q,0,q,x.se);
cursum+=x.se;
}
if(tl==tr){
int l = 0,r = q;
//cout<<tl<<" "<<mnn[1]<<" "<<mxx[1]<<'\n';
while(r>=l){
int mid = (l+r)/2;
ll rmn = mnquery(1,mid,q,0,q);
ll rmx = mxquery(1,mid,q,0,q);
if(rmx - rmn< C[tl])r = mid-1;
else l = mid+1;
}
if(r==-1){
ans[tl] = cursum - mnn[1];
return;
}
ll a = mnquery(1,r,q,0,q);
ll b = mxquery(1,r,q,0,q);
if(mnquery(1,r,r,0,q) == a)ans[tl] = C[tl] - (b - cursum);
else ans[tl] = cursum - a;
for(auto x:ch[v]){
upd(1,x.fi,q,0,q,-x.se);
cursum-=x.se;
}
return;
}
int tm = (tl+tr)/2;
solve(2*v,tl,tm);
solve(2*v+1,tm+1,tr);
for(auto x:ch[v]){
upd(1,x.fi,q,0,q,-x.se);
cursum-=x.se;
}
}
vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){
n = sz(c);
q = sz(l);
for(int i=0;i<n;i++)C[i] = c[i];
for(int i=0;i<q;i++)add(1,l[i],r[i],0,n-1,i,v[i]);
solve(1,0,n-1);
vector<int>tmp(n);
for(int i=0;i<n;i++)tmp[i] = ans[i];
return tmp;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
27224 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2208 ms |
83104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
21080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
27224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
27224 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
