Submission #435333

#	Time	Username	Problem	Language	Result	Execution time	Memory
435333		jangwonyoung	Distributing Candies (IOI21_candies)	C++17	100 / 100	608 ms	31500 KiB

candies

////////////////////////////////////////
#include "candies.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=2e5+5;
#define fi first
#define se second
int n,q;
vector<pair<int,int> >qr[N];
const int ts=1<<19;
ll mx[ts];
ll mn[ts];
ll sum[ts];
void pull(int id){
    sum[id]=sum[id*2]+sum[id*2+1];
    mx[id]=max(mx[id*2],mx[id*2+1]+sum[id*2]);
    mn[id]=min(mn[id*2],mn[id*2+1]+sum[id*2]);
}
void upd(int id,int l,int r,int p,ll v){
    if(l==r){
        mx[id]=0;
        mn[id]=0;
        sum[id]=v;
        if(v>0) mx[id]=v;
        else mn[id]=v;
        return;
    }
    int mid=(l+r)/2;
    if(p<=mid) upd(id*2,l,mid,p,v);
    else upd(id*2+1,mid+1,r,p,v);
    pull(id);
}
ll qry(int id,int l,int r,ll v,ll c){
    if(l==r){
        ll res=v+sum[id];
        res=min(res,c);
        res=max(res,0LL);
        return res;
    }
    int mid=(l+r)/2;
    if(mx[id*2+1]-mn[id*2+1]>=c){
        ll res=qry(id*2+1,mid+1,r,v,c);
        return res;
    }
    v=qry(id*2,l,mid,v,c);
    if(v+mx[id*2+1]>c){
        return c+sum[id*2+1]-mx[id*2+1];
    }
    if(v+mn[id*2+1]<0){
        return sum[id*2+1]-mn[id*2+1];
    }
    return v+sum[id*2+1];
}
vector<int>distribute_candies(vi c,vi l,vi r,vi v){
    n=c.size();q=l.size();
    vi ans(n);
    for(int i=0; i<q ;i++){
        qr[l[i]+1].push_back({i+1,v[i]});
        qr[r[i]+2].push_back({i+1,0});
    }
    for(int i=1; i<=n ;i++){
        for(auto c:qr[i]){
            upd(1,1,q,c.fi,c.se);
        }
        ans[i-1]=qry(1,1,q,0,c[i-1]);
    }
    return ans;
}

//////////////////////////////////////////

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33