Submission #1022128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022128		edogawa_something	Distributing Candies (IOI21_candies)	C++17	0 / 100	111 ms	29592 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define pb push_back
#define F first 
#define S second 
const ll M=2e5+10;
ll n,c,q,sz;
struct SEGTREE{
    vector<ll>res[3];
    vector<ll>pmi,pma;
    void init(ll x){
        sz=1;
        while(sz<x)
        sz*=2;
        pmi.resize(2*sz),pma.resize(2*sz);
        res[0].resize(2*sz),res[1].resize(2*sz),res[2].resize(2*sz);
    }
    void build(ll x=0,ll lx=0,ll rx=sz){
        ll mid=((lx+rx)>>1);
        res[0][x]=0,res[1][x]=0,pmi[x]=0,pma[x]=0,res[2][x]=c;
        if(rx-lx>1){
        build(x*2+1,lx,mid),build(x*2+2,mid,rx);
        }
    }
    void update(ll i,ll v,ll x=0,ll lx=0,ll rx=sz){
        if(rx-lx==1){
            pmi[x]=pma[x]=res[0][x]=res[1][x]=res[2][x]=v;
            pmi[x]=min(pmi[x],0ll),pmi[x]=max(pmi[x],-c);
            pma[x]=max(pma[x],0ll),pma[x]=min(pma[x],c);
            res[0][x]=pma[x];
            res[2][x]=c+pmi[x];
            res[1][x]=v;
            return;
        }
        ll mid=((lx+rx)>>1);
        if(i<mid)
        update(i,v,x*2+1,lx,mid);
        else
        update(i,v,x*2+2,mid,rx);
        ll lc=x*2+1,rc=x*2+2;
        res[1][x]=res[1][lc]+res[1][rc];
        pma[x]=max(pma[lc],res[1][lc]+pma[rc]);
        pmi[x]=min(pmi[lc],res[1][lc]+pmi[rc]);
        res[0][x]=res[0][lc],res[2][x]=res[2][lc];
        if(res[0][x]+pma[rc]<c&&res[0][x]+pmi[rc]>0){
        res[0][x]+=res[1][rc];
        }
        else if(res[0][x]+pma[rc]>=c){
        res[0][x]=res[2][rc];
        }
        else{
        res[0][x]=res[0][rc];
        }
        if(res[2][x]+pma[rc]<c&&res[2][x]+pmi[rc]>0)
        res[2][x]+=res[1][rc];
        else if(res[2][x]+pma[rc]>=c)
        res[2][x]=res[2][rc];
        else
        res[2][x]=res[0][rc];
    }

}seg;
vector<pair<int,int>>ql[M],qr[M];
vector<int> distribute_candies(vector<int>cc,vector<int>l,vector<int>r,vector<int>v){
    n=cc.size(),q=v.size();
    c=cc[0];
    seg.init(4);
    seg.build();
    vector<int>ans(n);
    for(int i=0;i<q;i++){
        ql[l[i]].pb({v[i],i});
        qr[r[i]].pb({v[i],i});
    }
    for(int i=0;i<n;i++){
        if(i>0)
        for(auto it:qr[i-1])
        seg.update(it.S,0);
        for(auto it:ql[i])
        seg.update(it.S,it.F);
        ans[i]=seg.res[0][0];
    }
    return ans;
}

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