Submission #1282805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282805		Faggi	Distributing Candies (IOI21_candies)	C++20	100 / 100	1149 ms	45140 KiB

candies

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

ll MIN=-1e15, MAX=1e15;

struct nodo
{
    ll lazy = 0, mi = MAX, ma = MIN;
};

vector<nodo> seg;
vector<ll> I, D;
ll pot = 1;

void upd(ll nod, ll x)
{
    seg[nod].lazy += x;
    seg[nod].mi+=x;
    seg[nod].ma+=x;
}

void prop(ll nod)
{
    ll x = seg[nod].lazy;
    if (nod < pot)
    {
        upd(nod*2,x);
        upd(nod*2+1,x);
    }
    seg[nod].lazy=0;
}

void up(ll nod)
{
    seg[nod].mi=min(seg[nod*2+1].mi,seg[nod*2].mi);
    seg[nod].ma=max(seg[nod*2+1].ma,seg[nod*2].ma);
}

void update(ll a, ll b, ll nod, ll x)
{
    if(I[nod]>b||D[nod]<a)
        return;
    if(I[nod]>=a&&D[nod]<=b)
    {
        upd(nod,x);
        return;
    }

    prop(nod);
    update(a,b,nod*2,x);
    update(a,b,nod*2+1,x);
    up(nod);
}
nodo calc(ll a, ll b, ll nod)
{
    if(I[nod]>b||D[nod]<a)
        return {0,MAX,MIN};
    if(I[nod]>=a&&D[nod]<=b)
        return seg[nod];
    prop(nod);
    nodo A=calc(a,b,nod*2), B=calc(a,b,nod*2+1), res;
    res.lazy=A.lazy+B.lazy;
    res.ma=max(A.ma,B.ma);
    res.mi=min(A.mi,B.mi);
    up(nod);
    return res;
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
    ll n = sz(C), q = sz(V), i;
    while (pot < q+1)
        pot *= 2;
    seg.resize(pot * 2);
    I.resize(pot * 2);
    D.resize(pot * 2);

    for (i = pot; i < pot * 2; i++)
    {
        I[i] = D[i] = i;
        seg[i].mi=seg[i].ma=0;
    }
    for (i = pot - 1; i > 0; i--)
    {
        I[i] = I[i * 2];
        D[i] = D[i * 2 + 1];
        seg[i].mi=seg[i].ma=0;
    }

    vector<pair<ll, pair<ll, pair<ll,ll>>>> qs;
    for (i = 0; i < q; i++)
        qs.pb({L[i], {R[i], {V[i],i+1}}});
    sort(all(qs));
    reverse(all(qs));

    priority_queue<pair<ll,pair<ll,ll>>>fins;
    vector<int> ans(n);

    for (i = 0; i < n; i++)
    {
        while(fins.size()&&-fins.top().fr<i)
        {
            update(fins.top().se.se+pot,pot*2-1,1,-fins.top().se.fr);
            fins.pop();
        }
        while(qs.size()&&qs.back().fr<=i)
        {
            fins.push({-qs.back().se.fr,{qs.back().se.se.fr,qs.back().se.se.se}});
            update(qs.back().se.se.se+pot,pot*2-1,1,qs.back().se.se.fr);
            qs.pop_back();
        }
        ll l=0, r=q, piv, pos=0;
        nodo a=seg[1];
        if(a.ma-a.mi<C[i])//caso facil
        {
            ll ami=a.mi;
            a=calc(pot+q,pot+q,1);
            ans[i]=a.lazy-ami;
            continue;
        }
        while(l<=r)
        {
            piv=(l+r)/2;
            a=calc(pot+piv,pot*2-1,1);
            if(a.ma-a.mi>=C[i])
            {
                l=piv+1;
                pos=piv;
            }
            else
                r=piv-1;
        }

        a=calc(pot+pos,pot*2-1,1);
        nodo b=calc(pot+q,pot+q,1), c=calc(pot+pos,pot+pos,1);
        if(c.lazy==a.mi)
            ans[i]=C[i]-(a.ma-b.lazy);
        else
            ans[i]=b.lazy-a.mi;

    }

    return ans;
}

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