Submission #721122

#	Time	Username	Problem	Language	Result	Execution time	Memory
721122		urosk	Distributing Candies (IOI21_candies)	C++17	3 / 100	5053 ms	23096 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define pll pair<ll,ll>
#define fi first
#define sc second
#define dbg(x) cerr<#x<<": "<<x<<endl;

using namespace std;
#define maxn 200005
ll n,q;
ll a[maxn],c[maxn];
vector<pll> t[2*maxn];
ll ls[2*maxn],rs[2*maxn],root = 0,tsz = 0;
void init(ll &v,ll tl,ll tr){
    t[v].clear();
    if(!v) v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
void upd(ll v,ll tl,ll tr,ll l,ll r,pll p){
    if(l>r||tl>tr||l>tr||tl>r) return;
    if(tl>=l&&tr<=r){t[v].pb(p);return;}
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,p);
    upd(rs[v],mid+1,tr,l,r,p);
}
set<pll> cur;
void reshi(ll v,ll tl,ll tr){
    for(pll p : t[v]) cur.insert(p);
    ll mid = (tl+tr)/2;
    if(tl==tr){
        ll i = tl;
        for(pll p : cur){
            a[i]+=p.sc;
            if(a[i]<0) a[i] = 0;
            if(a[i]>c[i]) a[i] = c[i];
        }
        goto lol;
    }
    reshi(ls[v],tl,mid);
    reshi(rs[v],mid+1,tr);
    lol:;
    for(pll p : t[v]){
        cur.erase(cur.find(p));
    }
}
ll d = 400;
vector<int> ans;
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> VAL) {
    n = C.size();
    q = L.size();
    for(ll i = 1;i<=n;i++) c[i] = C[i-1];
    sort(a+1,a+1+n);
    init(root,1,n);
    for(ll i = 1;i<=q;i++){
        ll l = L[i-1] + 1;
        ll r = R[i-1] + 1;
        ll val = VAL[i-1];
        if(i%d==0){
            reshi(root,1,n);
            init(root,1,n);
        }
        upd(root,1,n,l,r,{i,val});
    }
    reshi(root,1,n);
    for(ll i = 1;i<=n;i++) ans.pb(a[i]);
    return ans;
}

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