| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 571374 | kshitij_sodani | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
#include "candies.h"
#include <vector>
llo tree[4*200001][4];
llo lazy[4*200001];
//min
//max
//max-min
vector<pair<int,int>> pre[200001];
vector<pair<int,int>> pre2[200001];
void push(int no,int l,int r){
tree[no][0]+=lazy[no];
tree[no][1]+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
void update(int no,int l,int r,int aa,int bb,int x){
push(no,l,r);
if(l>bb or r<aa or aa>bb){
return;
}
if(aa<=l and r<=bb){
lazy[no]+=x;
push(no,l,r);
}
else{
int mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,x);
update(no*2+2,mid+1,r,aa,bb,x);
tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
tree[no][2]=min(tree[no*2+1][2],tree[no*2+2][2]);
tree[no][2]=min(tree[no][2],tree[no*2+2][0]-tree[no*2+1][1]);
tree[no][3]=max(tree[no*2+1][3],tree[no*2+2][3]);
tree[no][3]=max(tree[no][3],tree[no*2+2][1]-tree[no*2+1][0]);
}
}
llo query(int no,int l,int r,int aa,int bb){
push(no,l,r);
if(r<aa or l>bb or aa>bb){
return (llo)1e18;
}
if(aa<=l and r<=bb){
return tree[no][0];
}
int mid=(l+r)/2;
return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
vector<int> ans;
int q=l.size();
for(int i=0;i<q;i++){
pre[l[i]].pb({i,v[i]});
}
for(int i=0;i<q;i++){
pre2[r[i]].pb({i,v[i]});
}
llo su=0;
for(int i=0;i<n;i++){
for(auto j:pre[i]){
update(0,0,q,j.a+1,q,j.b);
su+=j.b;
}
llo ind=0;
if(tree[0][2]<=-c[i]){
llo no=0;
pair<llo,llo> cur={0,q};
llo ma=0;
while(cur.a<cur.b){
int mid=(cur.a+cur.b)/2;
llo ok=0;
if(tree[no*2+2][0]-tree[no*2+1][1]<=-c[i]){
ok=1;
}
if(tree[no*2+2][2]<=-c[i]){
ok=1;
}
if(tree[no*2+2][2]-ma<=-c[i]){
ok=1;
}
if(ok==1){
ma=max(ma,tree[no*2+1][1]);
cur={mid+1,cur.b};
no*=2;
no+=2;
continue;
}
cur={cur.a,mid};
no=no*2+1;
}
if(tree[no][0]-ma<=-c[i]){
ind=cur.a;
}
}
llo ind2=0;
if(tree[0][3]>=c[i]){
llo no=0;
pair<llo,llo> cur={0,q};
llo ma=0;
while(cur.a<cur.b){
/*if(i==2){
cout<<cur.a<<","<<cur.b<<endl;
}*/
/*if(i==1){
cout<<cur.a<<","<<cur.b<<":"<<ma<<endl;
}*/
int mid=(cur.a+cur.b)/2;
push(no,cur.a,cur.b);
push(no*2+1,cur.a,mid);
push(no*2+2,mid+1,cur.b);
llo ok=0;
if(tree[no*2+2][1]-tree[no*2+1][0]>=c[i]){
ok=1;
}
/*if(i==2){
cout<<ok<<','<<endl;
cout<<tree[no*2+2][1]-tree[no*2+1][0]<<"::"<<endl;
}*/
if(tree[no*2+2][3]>=c[i]){
ok=1;
}
/* if(i==2){
cout<<ok<<','<<endl;
}*/
if(tree[no*2+2][3]-ma>=c[i]){
ok=1;
}
/*if(i==2){
cout<<ok<<','<<endl;
}*/
if(ok==1){
ma=min(ma,tree[no*2+1][0]);
cur={mid+1,cur.b};
no*=2;
no+=2;
continue;
}
cur={cur.a,mid};
no=no*2+1;
}
if(i==2){
//cout<<no<<",,"<<endl;
//cout<<tree[no][1]<<",,"<<ma<<endl;
}
if(tree[no][1]-ma>=c[i]){
ind2=cur.a;
}
//cout<<11<<endl;
}
//cout<<i<<":"<<ind<<":"<<ind2<<endl;
assert(ind==0);
ans2.pb(min(su,c[i]));
continue;
if(ind2>ind){
llo ans2=c[i]+su-query(0,0,q,ind2,ind2);
ans.pb(ans2);
}
else{
llo ans2=su-query(0,0,q,ind,ind);
ans.pb(ans2);
}
/*if(ind>q){
ans.pb(0);
}
else{
//query max suffx sum in ind+1,q range
ans.pb(su-query(0,0,n-1,ind,q));
}*/
for(auto j:pre2[i]){
update(0,0,q,j.a+1,q,-j.b);
su-=j.b;
}
}
return ans;
}