# include <bits/stdc++.h>
#include "candies.h"
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
const int N=2e5+5;
ll n,q,le,ri,mid,ans,c,idx,idx1;
ll C[N],cc[N],lz[4*N],L[N],R[N],V[N];
vector <int> vans;
vector < pair <ll,ll> > v[N];
struct nd {
ll mx;
ll mn;
ll sum;
ll mxidx;
ll mnidx;
};
nd ndd,tree[4*N];
nd merge(nd x,nd y) {
nd mr;
mr.mx=max(x.mx,y.mx);
mr.mn=min(x.mn,y.mn);
mr.sum=x.sum+y.sum;
if(x.mx>=y.mx) mr.mxidx=x.mxidx;
else mr.mxidx=y.mxidx;
if(x.mn<=y.mn) mr.mnidx=x.mnidx;
else mr.mnidx=y.mnidx;
return mr;
}
void build(ll node,ll le,ll ri) {
if(le==ri) {
tree[node].mx=0;
tree[node].mn=0;
tree[node].sum=0;
tree[node].mxidx=le;
tree[node].mnidx=le;
return;
}
build(2*node,le,(le+ri)/2);
build(2*node+1,(le+ri)/2+1,ri);
tree[node]=merge(tree[2*node],tree[2*node+1]);
}
void update(ll node,ll le,ll ri,ll start,ll end,ll val) {
if(lz[node]) {
tree[node].mx+=lz[node];
tree[node].mn+=lz[node];
tree[node].sum+=lz[node]*(ri-le+1);
if(le!=ri) {
lz[2*node]+=lz[node];
lz[2*node+1]+=lz[node];
}
lz[node]=0;
}
if(ri<start || le>end) return;
if(start<=le && ri<=end) {
tree[node].mx+=val;
tree[node].mn+=val;
tree[node].sum+=val*(ri-le+1);
if(le!=ri) {
lz[2*node]+=val;
lz[2*node+1]+=val;
}
return;
}
update(2*node,le,(le+ri)/2,start,end,val);
update(2*node+1,(le+ri)/2+1,ri,start,end,val);
tree[node]=merge(tree[2*node],tree[2*node+1]);
}
nd get(ll node,ll le,ll ri,ll start,ll end) {
if(lz[node]) {
tree[node].mx+=lz[node];
tree[node].mn+=lz[node];
tree[node].sum+=lz[node]*(ri-le+1);
if(le!=ri) {
lz[2*node]+=lz[node];
lz[2*node+1]+=lz[node];
}
lz[node]=0;
}
if(le>end || ri<start) return ndd;
if(start<=le && ri<=end) {
return tree[node];
}
return merge(get(2*node,le,(le+ri)/2,start,end),get(2*node+1,(le+ri)/2+1,ri,start,end));
}
bool go(ll x) {
if(get(1,0,q,x,q).mx-get(1,0,q,x,q).mn>=c) return 1;
else return 0;
}
vector<int> distribute_candies(vector<int> cc, vector<int> lll, vector<int> rr, vector<int> vall) {
n=cc.size(); q=lll.size();
ndd.mx=-1e18;
ndd.mn=1e18;
for(ll i=0;i<n;i++) {
C[i+1]=cc[i];
}
for(ll i=0;i<q;i++) {
L[i+1]=lll[i]+1;
R[i+1]=rr[i]+1;
V[i+1]=vall[i];
}
for(ll i=1;i<=q;i++) {
v[L[i]].pb({i,V[i]});
v[R[i]+1].pb({i,-V[i]});
}
build(1,0,q);
for(ll i=1;i<=n;i++) {
for(ll j=0;j<v[i].size();j++){
update(1,0,q,v[i][j].f,q,v[i][j].sc);
}
c=C[i];
le=0; ri=q; ans=0;
while(le<=ri) {
mid=(le+ri)/2;
if(go(mid)) { le=mid+1; ans=mid; }
else ri=mid-1;
}
idx=get(1,0,q,ans,q).mnidx;
idx1=get(1,0,q,ans,q).mxidx;
//cout<<ans<<" "<<idx<<" "<<idx1<<endl;
if(idx>=idx1) {
vans.pb(get(1,0,q,q,q).sum-get(1,0,q,idx,idx).sum);
} else {
vans.pb(c+get(1,0,q,q,q).sum-get(1,0,q,idx1,idx1).sum);
}
}
return vans;
}/*
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> c(n);
for(int i = 0; i < n; ++i) {
assert(scanf("%d", &c[i]) == 1);
}
int q;
assert(1 == scanf("%d", &q));
std::vector<int> l(q), r(q), v(q);
for(int i = 0; i < q; ++i) {
assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
}
std::vector<int> ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}*/
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:110:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(ll j=0;j<v[i].size();j++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
5452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2292 ms |
55512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
5452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
