Submission #1049027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049027		Malix	Distributing Candies (IOI21_candies)	C++17	11 / 100	266 ms	9052 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,ll,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vector<ll> ft;
int n,q;
vi a,st,loc,st2,loc2;
int mx=1e9;

void update(int x,ll y){
    x++;
    while(x<n+1){
        ft[x]+=y;
        x+=LSOne(x);
    }
}

ll solve(int x){
    x++;
    ll ans=0;
    while(x){
        ans+=ft[x];
        x-=LSOne(x);
    }
    return ans;
}

void build(int x,int l,int r){
    if(l==r){
        st[x]=a[l];
        loc[x]=l;
        st2[x]=a[l];
        loc2[x]=-l;
        return;
    }
    int m=(l+r)/2;
    build(2*x,l,m);
    build(2*x+1,m+1,r);
    st[x]=max(st[2*x],st[2*x+1]);
    st2[x]=min(st2[2*x],st2[2*x+1]);
    if(st[2*x]<=st[2*x+1])loc[x]=loc[2*x+1];
    else loc[x]=loc[2*x];
    if(st2[2*x]>=st2[2*x+1])loc2[x]=loc2[2*x+1];
    else loc2[x]=loc2[2*x];
}

pi maximum(int x,int l,int r,int a,int b){
    if(a>b)return {-1,-1};
    if(l==a&&r==b)return {st[x],loc[x]};
    int m=(l+r)/2;
    return max(maximum(2*x,l,m,a,min(b,m)),maximum(2*x+1,m+1,r,max(a,m+1),b));
}

pi minimum(int x,int l,int r,int a,int b){
    if(a>b)return {inf,inf};
    if(l==a&&r==b)return {st2[x],loc2[x]};
    int m=(l+r)/2;
    return min(minimum(2*x,l,m,a,min(b,m)),minimum(2*x+1,m+1,r,max(a,m+1),b));
}

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();
if(n<=2000){
    vi ans(n,0);
    REP(i,0,q)REP(j,l[i],r[i]+1)ans[j]=max(0,min(c[j],ans[j]+v[i]));
    return ans;
}
    bool flag=1;
    REP(i,0,n)if(v[i]<0)flag=0;
if(flag){
    vi ans(n);
    ft.resize(n+1,0);
    REP(i,0,q){
        update(l[i],(ll)v[i]);
        update(r[i]+1,(ll)(-v[i]));
    }
    REP(i,0,n){
        ll x=solve(i);
        if(x>1e9)x=1e9;
        ans[i]=min(c[i],(int)x);
    }
    return ans;
}
    int pos=0;
    ll tot=0;
    flag=0;
    while(pos<q){
        while(pos<q&&v[pos]>0){
            tot+=v[pos];
            pos++;
        }
        a.PB(tot);
        if(tot>=mx){
            a.clear();
            flag=1;
            tot=mx;
        }
        while(pos<q&&v[pos]<0){
            tot+=v[pos];
            pos++;
        }
        a.PB(tot);
        if(tot<=0){
            a.clear();
            flag=0;
            tot=0;
        }
    }
    int m=a.size();
    if(m==0){
        vi ans(n);
        if(flag)REP(i,0,n)ans[i]=c[i];
        else REP(i,0,n)ans[i]=0;
        return ans;
    }
    st.resize(4*m+1);loc.resize(4*m+1);
    st2.resize(4*m+1);loc2.resize(4*m+1);
    build(1,0,m-1);
    pos=0;int lval=0,rval=1e9;
    vector<tii> arr;
    if(flag){
        pi val=minimum(1,0,m-1,pos,m-1);
        lval=val.F;pos=-val.S+1;
        arr.PB({rval-lval,a[m-1]-(-val.S-1<0?0:a[-val.S-1]),1});
    }
    while(pos<m){
        pi val=maximum(1,0,m-1,pos,m-1);
        rval=val.F;pos=val.S+1;
        arr.PB({rval-lval,a[m-1]-(val.S-1<0?0:a[val.S-1]),0});
        if(pos>=m)break;
        val=minimum(1,0,m-1,pos,m-1);
        lval=val.F;pos=-val.S+1;
        arr.PB({rval-lval,a[m-1]-(-val.S-1<0?0:a[-val.S-1]),1});
    }
    arr.PB({0,0,0});
    reverse(arr.begin(),arr.end());
    vi ans(n);
    REP(i,0,n){
        tuple<int,ll,int> temp={c[i],-1,-1};
        auto it=upper_bound(arr.begin(),arr.end(),temp);
        it--;
        ll x=get<1>(*it);
        int y=get<2>(*it);
        if(y==1)ans[i]=c[i];
        else ans[i]=0;
        ans[i]+=(int)x;
    }
    return ans;
}

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