Submission #1277304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277304		Faggi	Distributing Candies (IOI21_candies)	C++20	0 / 100	1012 ms	64944 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 inMa2 = LLONG_MIN, inMa1 = 0;
ll inMi2=LLONG_MAX, inMi1=0;

struct nodo
{
    ll sum = 0, lazy = 0, ma1 = inMa1, ma2 = inMa2, tam = 0, cma1 = 0, cma2 = 0;
    ll mi1=inMi1, mi2=inMi2, cmi1=0, cmi2=0;
    bool laz=0, laz2=0;
};

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

void newMa1(ll nod, ll val)
{
    seg[nod].sum -= seg[nod].cma1 * seg[nod].ma1;
    seg[nod].ma1 = val;
    seg[nod].sum += seg[nod].cma1 * seg[nod].ma1;
    seg[nod].laz=1;
}

void newMi1(ll nod, ll val)
{
    seg[nod].sum-=seg[nod].cmi1*seg[nod].mi1;
    seg[nod].mi1=val;
    seg[nod].sum+=seg[nod].cmi1*seg[nod].mi1;
    seg[nod].laz2=1;
}

void act(ll nod, ll val)
{
    ll pad = nod / 2;
    seg[nod].sum += val * seg[nod].tam;
    seg[nod].lazy += val;
    if(seg[nod].ma1!=inMa2)
        seg[nod].ma1 += val;
    if(seg[nod].ma2!=inMa2)
        seg[nod].ma2 += val;
    if(seg[nod].mi1!=inMi2)
        seg[nod].mi1+=val;
    if(seg[nod].mi2!=inMi2)
        seg[nod].mi2+=val;
    if (seg[nod].ma1 > seg[pad].ma1 && seg[pad].laz)
    {
        if(seg[nod].ma1==seg[nod].mi1)
            seg[nod].mi1=seg[pad].ma1;
        newMa1(nod,seg[pad].ma1);
    }
    if(seg[nod].mi1<seg[pad].mi1 &&seg[pad].laz2)
    {
        if(seg[nod].ma1==seg[nod].mi1)
            seg[nod].ma1=seg[pad].mi1;
        newMi1(nod,seg[pad].mi1);
    }
}

void prop(ll nod)
{
    act(nod * 2, seg[nod].lazy);
    act(nod * 2 + 1, seg[nod].lazy);
    seg[nod].lazy = 0;
    seg[nod].laz=0;
    seg[nod].laz2=0;
}

ll sum(ll nod, ll x)
{
    ll ret = 0;
    for (ll i = 0; i < 2; i++)
    {
        if (seg[nod * 2 + i].ma1 == x)
            ret = ret + seg[nod * 2 + i].cma1;
        if (seg[nod * 2 + i].ma2 == x)
            ret = ret + seg[nod * 2 + i].cma2;
    }
    return ret;
}

ll sum2(ll nod, ll x)
{
    ll ret = 0;
    for (ll i = 0; i < 2; i++)
    {
        if (seg[nod * 2 + i].mi1 == x)
            ret = ret + seg[nod * 2 + i].cmi1;
        if (seg[nod * 2 + i].mi2 == x)
            ret = ret + seg[nod * 2 + i].cmi2;
    }
    return ret;
}
void up(ll nod)
{
    vector<ll> v = {seg[nod * 2].ma1, seg[nod * 2 + 1].ma1, seg[nod * 2].ma2, seg[nod * 2 + 1].ma2};
    sort(all(v));
    auto it =unique(all(v));
    ll fin = (it-v.begin())-1, i;
    seg[nod].ma1 = v[fin];
    fin--;
    if (fin >= 0)
        seg[nod].ma2 = v[fin];
    else
        seg[nod].ma2 = inMa2;

    seg[nod].cma1 = sum(nod, seg[nod].ma1);
    seg[nod].cma2 = sum(nod, seg[nod].ma2);

    seg[nod].sum = seg[nod * 2].sum + seg[nod * 2 + 1].sum;

    v = {seg[nod * 2].mi1, seg[nod * 2 + 1].mi1, seg[nod * 2].mi2, seg[nod * 2 + 1].mi2};
    sort(all(v));
    it =unique(all(v));
    fin = (it-v.begin())-1;
    seg[nod].mi1=v[0];
    seg[nod].cmi1=sum2(nod,seg[nod].mi1);
    
    if(fin>0)
        seg[nod].mi2=v[1];
    else
        seg[nod].mi2=inMi2;
    seg[nod].cmi2 = sum2(nod, seg[nod].mi2);
}

void update(ll l, ll r, ll nod, ll val)
{
    if (I[nod] > r || D[nod] < l)
        return;
    if (I[nod] >= l && D[nod] <= r)
    {
        act(nod, val);
        return;
    }
    prop(nod);
    update(l, r, nod * 2, val);
    update(l, r, nod * 2 + 1, val);
    up(nod);
}

ll calc(ll l, ll r, ll nod)
{
    if (I[nod] > r || D[nod] < l)
        return 0;
    if (I[nod] >= l && D[nod] <= r)
        return seg[nod].sum;
    prop(nod);
    ll ret = calc(l, r, nod * 2) + calc(l, r, nod * 2 + 1);
    return ret;
}

void chmin(ll nod, ll val)
{
    if (seg[nod].ma1 <= val)
        return;
    if (seg[nod].ma2 < val)
    {
        newMa1(nod, val);
        if(seg[nod].mi1>val)
            seg[nod].mi1=val;
        return;
    }
    prop(nod);
    chmin(nod * 2, val);
    chmin(nod * 2 + 1, val);
    up(nod);
}

void chmax(ll nod, ll val)
{
    if(seg[nod].mi1>=val)
        return;
    if(seg[nod].mi2>val)
    {
        newMi1(nod,val);
        if(seg[nod].ma1<val)
            seg[nod].ma1=val;
        return;
    }
    prop(nod);
    chmax(nod*2,val);
    chmax(nod*2+1,val);
    up(nod);
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v)
{
    ll i;
    n = sz(c);
    q = sz(l);
    while (pot < n)
        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].ma1=inMa2;
        seg[i].mi1=inMi2;
    }

    for (i = 0; i < n; i++)
    {
        seg[i+pot].ma1=0;
        seg[i+pot].mi1=0;
        seg[i+pot].cmi1=seg[i + pot].cma1 = seg[i + pot].tam = 1;
    }

    for (i = pot - 1; i > 0; i--)
    {
        I[i] = I[i * 2];
        D[i] = D[i * 2 + 1];
        seg[i].cmi1=seg[i].cma1 = seg[i].tam = seg[i * 2].tam + seg[i * 2 + 1].tam;
    }

    for (i = 0; i < q; i++)
    {
        update(l[i] + pot, r[i] + pot, 1, v[i]);
        chmin(1,c[0]);
        chmax(1,0);
        /*for (ll j = 0; j < 3; j++)
        {
            for (ll k = j; k < 3; k++)
            {
                cout << j << ' ' << k << ": " << calc(j + pot, k + pot, 1) << '\n';
            }
        }*/
    }
    vector<int>ans(n);
    for(i=0; i<n; i++)
        ans[i]=calc(i+pot,i+pot,1);
    return ans;
}

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