Submission #721206

#	Time	Username	Problem	Language	Result	Execution time	Memory
721206		n0sk1ll	Distributing Candies (IOI21_candies)	C++17	100 / 100	629 ms	36396 KiB

candies

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const li inf=1e18;

li mn[550001],mx[550001],upd[550001];
int l[550001],r[550001],k=1;

void Upd(int p)
{
    mn[p]+=upd[p],mx[p]+=upd[p];
    if (p<k) upd[2*p]+=upd[p],upd[2*p+1]+=upd[p];
    upd[p]=0;
}

void Add(int p, int ll, int rr, int x)
{
    if (rr<l[p] || ll>r[p]) Upd(p);
    else if (ll<=l[p] && rr>=r[p]) upd[p]+=x,Upd(p);
    else Upd(p),Add(2*p,ll,rr,x),Add(2*p+1,ll,rr,x),mn[p]=min(mn[2*p],mn[2*p+1]),mx[p]=max(mx[2*p],mx[2*p+1]);
}

vector<int> cvorovi;
void rastavi(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return;
    if (ll<=l[p] && rr>=r[p]) Upd(p),cvorovi.pb(p);
    else Upd(p),rastavi(2*p,ll,rr),rastavi(2*p+1,ll,rr);
}

int WalkRaz(int p, int x, li tmn, li tmx)
{
    Upd(p);
    if (max(tmx,mx[p])-min(tmn,mn[p])<x) return -1;
    if (p>=k) return p-k;
    int mozda=WalkRaz(2*p+1,x,tmn,tmx);
    if (mozda==-1) return WalkRaz(2*p,x,min(tmn,mn[2*p+1]),max(tmx,mx[2*p+1]));
    return mozda;
}

int WalkMin(int p)
{
    Upd(p);
    if (p>=k) return p-k;
    Upd(2*p),Upd(2*p+1);
    if (mn[p]==mn[2*p+1]) return WalkMin(2*p+1);
    return WalkMin(2*p);
}

int WalkMax(int p)
{
    Upd(p);
    if (p>=k) return p-k;
    Upd(2*p),Upd(2*p+1);
    if (mx[p]==mx[2*p+1]) return WalkMax(2*p+1);
    return WalkMax(2*p);
}

void ispisi()
{
    ff(i,1,2*k) Upd(i);
    for (int kk=1;kk<=k;kk*=2)
    {
        ff(i,kk,2*kk) cout<<"("<<mn[i]<<","<<mx[i]<<") ";
        cout<<endl;
    } cout<<endl;
}

vector<pair<bool,pii>> qry[200005]; //add (or remove) : time kad dodajemo : sta dodajemo (potenicjalno negativno)

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
    int n=(int)C.size();
    int q=(int)V.size();

    while (k<q) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,q,k) mn[i+k]=inf,mx[i+k]=-inf;
    bff(i,1,k) mn[i]=min(mn[2*i],mn[2*i+1]);
    bff(i,1,k) mx[i]=max(mx[2*i],mx[2*i+1]);

    ff(i,0,q)
    {
        qry[L[i]].pb({1,{i,V[i]}});
        qry[R[i]+1].pb({0,{i,V[i]}});
    }

    vector<int> ans(n,0);

    li suma=0;
    ff(i,0,n)
    {
        for (auto it : qry[i])
        {
            bool dodajem=it.xx;
            int kad=it.yy.xx;
            int sta=it.yy.yy;

            if (dodajem) Add(1,kad,q-1,sta),suma+=sta;
            else Add(1,kad,q-1,-sta),suma-=sta;
        }

        Upd(1);

        //ispisi();

        if (mx[1]-mn[1]<=C[i])
        {
            if (mx[1]>C[i]) ans[i]=C[i]-(mx[1]-suma);
            else
            {
                int djemin=WalkMin(1);
                if (mn[djemin+k]<0) ans[i]=suma-mn[djemin+k];
                else ans[i]=suma;
            }
        }
        else
        {
            int dje=WalkRaz(1,C[i],inf,-inf);

            rastavi(1,dje,q-1);
            int mp=cvorovi[0];
            for (auto p : cvorovi) if (mn[p]<mn[mp]) mp=p;
            int djemin=WalkMin(mp);

            mp=cvorovi[0];
            for (auto p : cvorovi) if (mx[p]>mx[mp]) mp=p;
            int djemax=WalkMax(mp);
            cvorovi.clear();

            if (djemin>djemax) ans[i]=min((li)C[i],suma-mn[djemin+k]);
            else ans[i]=max(0ll,C[i]-(mx[djemax+k]-suma));
        }
    }

    return ans;
}

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