#include "bits/stdc++.h"
#include "candies.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const long long INF = 1e18;
struct SegT_Min{
int n;
vector<long long> t;
SegT_Min(int nn){
n=nn;
t.assign(4*n+5,INF);
}
void upd(int rt,int l,int r,int ind,long long u){
if(r<ind || l>ind) return;
if(l==r){
t[rt]=min(t[rt],u);
return;
}
int m=(l+r)/2;
upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u);
t[rt]=min(t[rt*2],t[rt*2+1]);
}
long long query(int rt,int l,int r,int gl,int gr){
if(r<gl || l>gr) return INF;
if(l>=gl && r<=gr) return t[rt];
int m=(l+r)/2;
return min(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
}
};
struct SegT_Max{
int n;
vector<long long> t;
SegT_Max(int nn){
n=nn;
t.assign(4*n+5,-INF);
}
void upd(int rt,int l,int r,int ind,long long u){
if(r<ind || l>ind) return;
if(l==r){
t[rt]=max(t[rt],u);
return;
}
int m=(l+r)/2;
upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u);
t[rt]=max(t[rt*2],t[rt*2+1]);
}
long long query(int rt,int l,int r,int gl,int gr){
if(r<gl || l>gr) return -INF;
if(l>=gl && r<=gr) return t[rt];
int m=(l+r)/2;
return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
}
};
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
int n=sz(C),q=sz(V);
vector<int> ans(n);
vector<array<long long,2>> c;
for(int i=0;i<n;i++) c.push_back({C[i],i});
sort(all(c));
long long pre[q+5];
pre[0]=0;
for(int i=1;i<=q;i++) pre[i]=pre[i-1]+V[i-1];
SegT_Min t1(q);SegT_Max t2(q);
for(int i=0;i<=q;i++){
t1.upd(1,1,q,i,pre[i]);
t2.upd(1,1,q,i,pre[i]);
}
long long p=0,cur=0;
for(int i=n-1;i>=0;i--){
long long cap=c[i][0];
cur=min(cur,cap);
while(p<q){
int l=p+1,r=q+1;
while(l<r){
int m=(l+r)/2;
if(t1.query(1,1,q,p+1,m)<=pre[p]-cur) r=m;
else l=m+1;
}
int ans0=l;
l=p+1,r=q+1;
while(l<r){
int m=(l+r)/2;
if(t2.query(1,1,q,p+1,m)>=cap-cur-pre[p]) r=m;
else l=m+1;
}
int ansm=l;
if(ansm==q+1 && ans0==q+1) break;
p=min(ansm,ans0);
if(ans0<=ansm) cur=0;
else cur=cap;
}
ans[c[i][1]]=cur+pre[q]-pre[p];
}
return ans;
}
/*void _(){
int n,q;
cin >> n >> q;
vector<array<int,2>> c;
for(int i=1;i<=n;i++){
int a;cin >> a;
c.push_back({a,i});
}
int xd[q+5],ans[n+5],pre[q+5];
pre[0]=0;
for(int i=1;i<=q;i++){
cin >> xd[i];
pre[i]=pre[i-1]+xd[i];
}
sort(all(c));
SegT_Min t1(q);SegT_Max t2(q);
for(int i=0;i<=q;i++){
t1.upd(1,1,q,i,pre[i]);
t2.upd(1,1,q,i,pre[i]);
}
int p=0,cur=0;
for(int i=n-1;i>=0;i--){
int cap=c[i][0];
cur=min(cur,cap);
while(p<q){
int l=p+1,r=q+1;
while(l<r){
int m=(l+r)/2;
if(t1.query(1,1,q,p+1,m)<=pre[p]-cur) r=m;
else l=m+1;
}
int ans0=l;
l=p+1,r=q+1;
while(l<r){
int m=(l+r)/2;
if(t2.query(1,1,q,p+1,m)>=cap-cur-pre[p]) r=m;
else l=m+1;
}
int ansm=l;
if(ansm==q+1 && ans0==q+1) break;
p=min(ansm,ans0);
if(ans0<=ansm) cur=0;
else cur=cap;
}
ans[c[i][1]]=cur+pre[q]-pre[p];
}
for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n];
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 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 |
636 ms |
25240 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 |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
