This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int off=1,t[500005],t1[500005],p[500005],n,q;
void send(int x) {
if(!p[x]) return;
t[x]=max(0,t[x]-p[x]);
if(x<off) {
p[x*2]+=p[x];
p[x*2+1]+=p[x];
}
p[x]=0;
}
void update(int x,int lo,int hi,int l,int r,int v1) {
send(x);
if(lo>r || hi<l) return;
if(lo>=l && hi<=r) {
p[x]+=v1;
send(x);
return;
}
update(x*2,lo,(lo+hi)/2,l,r,v1);
update(x*2+1,(lo+hi)/2+1,hi,l,r,v1);
t[x]=max(t[x*2],t[x*2+1]);
}
int query(int x,int lo,int hi,int l,int r) {
send(x);
if(lo>r || hi<l) return 0;
if(lo>=l && hi<=r) return t[x];
return max(query(x*2,lo,(lo+hi)/2,l,r),query(x*2+1,(lo+hi)/2+1,hi,l,r));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
n=c.size();
q=l.size();
vector<int> s(n);
while(off<n) off*=2;
int mini=1e9;
for(int i=0;i<q;i++) mini=min(mini,v[i]);
if(mini>0) {
for(int i=0;i<n;i++) {
update(1,0,off-1,i,i,-c[i]);
}
for(int i=0;i<q;i++) {
update(1,0,off-1,l[i],r[i],v[i]);
}
for(int i=0;i<n;i++) {
s[i]=c[i]-query(1,0,off-1,i,i);
}
}
else if(n<=2000) {
for(int i=0;i<n;i++) {
s[i]=0;
}
for(int i=0;i<q;i++) {
if(v[i]<0) {
for(int j=l[i];j<=r[i];j++) {
s[j]=max(0,s[j]+v[i]);
}
}
else{
for(int j=l[i];j<=r[i];j++) {
s[j]=min(c[j],s[j]+v[i]);
}
}
}
}
return s;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |