Submission #1171843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171843		Math4Life2020	Distributing Candies (IOI21_candies)	C++20	100 / 100	2288 ms	43532 KiB

candies

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;

inline pii fzmax(pii p1, pii p2) {
    if (p1.first>p2.first) {
        return p1;
    }
    return p2;
}

inline pii fzmin(pii p1, pii p2) {
    if (p1.first<p2.first) {
        return p1;
    }
    return p2;
}

inline ll v2(ll x) {
    return __builtin_ctz(x);
}

const ll Nm = 262144; const ll E = 18;
ll minv[2*Nm];
ll minl[2*Nm];
ll maxv[2*Nm];
ll maxl[2*Nm];
ll lz[2*Nm]; //ALREADY APPLIED

void init() {
    for (ll i=0;i<(2*Nm);i++) {
        minv[i]=0;
        maxv[i]=0;
        lz[i]=0;
    }
    for (ll i=0;i<Nm;i++) {
        minl[i+Nm]=i;
        maxl[i+Nm]=i;
    }
    for (ll p=(Nm-1);p>=1;p--) {
        minl[p]=minl[2*p];
        maxl[p]=maxl[2*p];
    }
}

void lft(ll p0) {
    if (p0==0) {
        return;
    }
    assert(lz[p0]==0);
    //cout << "lz[p0="<<p0<<"]="<<lz[p0]<<"\n";
    if (p0<Nm) {
        if (minv[2*p0]<minv[2*p0+1]) {
            minv[p0]=minv[2*p0];
            minl[p0]=minl[2*p0];
        } else {
            minv[p0]=minv[2*p0+1];
            minl[p0]=minl[2*p0+1];
        }
        if (maxv[2*p0]>maxv[2*p0+1]) {
            maxv[p0]=maxv[2*p0];
            maxl[p0]=maxl[2*p0];
        } else {
            maxv[p0]=maxv[2*p0+1];
            maxl[p0]=maxl[2*p0+1];
        }
    }
}

void lftP(ll p0) {
    for (ll e=1;e<=E;e++) {
        if ((p0>>e)>0) {
            //cout << "lifting at "<<(p0>>e) << "\n";
            lft(p0>>e);
            // if (1) {
            //     cout << "maxv="<<maxv[p0>>e]<<", maxl="<<maxl[p0>>e]<<"\n";
            //     cout << "minv="<<minv[p0>>e]<<", minl="<<minl[p0>>e]<<"\n";
            // }
        }
    }
}

void pdn(ll p0) {
    if (lz[p0]!=0) {
        if (p0<Nm) {
            lz[2*p0]+=lz[p0];
            minv[2*p0]+=lz[p0];
            maxv[2*p0]+=lz[p0];
            lz[2*p0+1]+=lz[p0];
            minv[2*p0+1]+=lz[p0];
            maxv[2*p0+1]+=lz[p0];
        }
        lz[p0]=0;
    }
}

void pdnP(ll p0) {
    for (ll e=E;e>=0;e--) {
        if (p0>>e) {
            pdn(p0>>e);
        }
    }
}


void upd1(ll v0, ll p0) {
    pdnP(p0);
    lz[p0]+=v0;
    minv[p0]+=v0;
    maxv[p0]+=v0;
    lftP(p0);
}

void upd0(ll v0, ll x0) {
    if (x0>=Nm) {
        return;
    }
    assert(x0<Nm);
    ll vx = v2(Nm-x0);
    upd1(v0,(1LL<<(E-vx))+(x0>>vx));
    upd0(v0,x0+(1LL<<vx));
}

pii qrymax(ll a, ll b) { //{value, location}
    if (a>b) {
        return {-INF,-1};
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        ll pc = (a>>va)+(1<<(E-va));
        pdnP(pc);
        //cout << "pc="<<pc<<"\n";
        //cout << "max vals: "<<maxv[pc]<<","<<maxl[pc]<<"\n";
        return fzmax({maxv[pc],maxl[pc]},qrymax(a+(1<<va),b));
    } else {
        ll pc = (b>>vb)+(1<<(E-vb));
        pdnP(pc);
        //cout << "pc="<<pc<<"\n";
        //cout << "max vals: "<<maxv[pc]<<","<<maxl[pc]<<"\n";
        return fzmax({maxv[pc],maxl[pc]},qrymax(a,b-(1<<vb)));
    }
}

pii qrymin(ll a, ll b) {
    if (a>b) {
        return {INF,-1};
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        ll pc = (a>>va)+(1<<(E-va));
        pdnP(pc);
        //cout << "pc="<<pc<<"\n";
        //cout << "min vals: "<<minv[pc]<<","<<minl[pc]<<"\n";
        return fzmin({minv[pc],minl[pc]},qrymin(a+(1<<va),b));
    } else {
        ll pc = (b>>vb)+(1<<(E-vb));
        pdnP(pc);
        //cout << "pc="<<pc<<"\n";
        //cout << "min vals: "<<minv[pc]<<","<<minl[pc]<<"\n";
        return fzmin({minv[pc],minl[pc]},qrymin(a,b-(1<<vb)));
    }
}

ll qry0(ll c0) {
    //cout << "querying c0="<<c0<<"\n";
    ll xmin = -1; ll xmax = Nm-1;
    while (xmin!=xmax) {
        ll xtest = (xmin+xmax+1)/2;
        //cout << "xtest="<<xtest<<"\n";
        pii p1 = qrymin(xtest,Nm-1);
        //cout << "p1="<<p1.first<<","<<p1.second<<"\n";
        pii p2 = qrymax(xtest,Nm-1);
        //cout << "p2="<<p2.first<<","<<p2.second<<"\n";
        if (abs(p1.first-p2.first)>=c0) {
            xmin = xtest;
        } else {
            xmax = xtest-1;
        }
    }
    //cout << "xmin="<<xmin<<"\n";
    if (xmin==-1) {
        //return qrymax(Nm-1,Nm-1).first;
        ll v1 = qrymin(0,Nm-1).first;
        ll vf = qrymax(Nm-1,Nm-1).first;
        return (vf-v1);
    } else {
        pii p1 = qrymin(xmin,Nm-1);
        //cout << "p1="<<p1.first<<","<<p1.second<<"\n";
        pii p2 = qrymax(xmin,Nm-1);
        //cout << "p2="<<p2.first<<","<<p2.second<<"\n";
        ll vf = qrymax(Nm-1,Nm-1).first;
        //cout << "vf="<<vf<<"\n";
        if (p1.second>p2.second) { //min comes last
            return (vf-p1.first);
        } else {
            return (c0-p2.first+vf);
        }
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    init();
    ll N = c.size(); ll Q = l.size();
    vector<pii> updV[N+1];
    //store: {value to change by, starting index of update}
    for (ll q=0;q<Q;q++) {
        updV[l[q]].push_back({v[q],q+1});
        updV[r[q]+1].push_back({-v[q],q+1});
    }
    vector<int> ans;
    for (ll x=0;x<N;x++) {
        for (pii p0: updV[x]) {
            upd0(p0.first,p0.second);
        }
        ll ans1 = qry0(c[x]);
        //cout << ans1 << "\n";
        ans.push_back(ans1);
    }
    return ans;
}

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