Submission #1120862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120862		jerzyk	Distributing Candies (IOI21_candies)	C++17	100 / 100	512 ms	45892 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 2000'000'000'000'000'000LL;
const int II = 1'000'000'007;
const ll M = 1000'000'007LL;
const int N = 1<<18;
int tab[N], answer[N];

int que[N];
ll drz1[N * 2], drz2[N * 2], laz[2 * N], s = 0LL;

vector<int> qb[N], qe[N];

void Push(int v)
{
    for(int ne = v * 2; ne <= v * 2 + 1; ++ne)
    {
        drz1[ne] += laz[v];
        drz2[ne] += laz[v];
        laz[ne] += laz[v];
    }
    laz[v] = 0LL;
}

void Add(int v, int p, int k, int pz, int kz, ll x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        drz1[v] += x; drz2[v] += x;
        laz[v] += x;
        return;
    }
    Add(v * 2, p, (p + k) / 2, pz, kz, x);
    Add(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
    drz1[v] = min(drz1[v * 2], drz1[v * 2 + 1]) + laz[v];
    drz2[v] = max(drz2[v * 2], drz2[v * 2 + 1]) + laz[v];
}

void A(int pos, int x)
{
    s += (ll)x;
    Add(1, 0, N - 1, pos, N - 1, x);
}

int Calc(ll x, int q)
{
    int v = 1;
    ll mi = I, ma = -I, mi1;
    while(v < N)
    {
        Push(v);
        if(max(ma, drz2[v * 2 + 1]) - min(mi, drz1[v * 2 + 1]) <= x)
        {
            ma = max(ma, drz2[v * 2 + 1]);
            mi = min(mi, drz1[v * 2 + 1]);
            v = v * 2;
        }else
            v = v * 2 + 1;
    }
    mi1 = mi;
    mi = min(mi, drz1[v]); ma = max(ma, drz2[v]);
    if(mi == mi1)
        return (s - mi);
    else
        return x + (s - ma);
}

void DoA(int n, int q)
{
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j < (int)qb[i].size(); ++j)
            A(qb[i][j], que[qb[i][j]]);
        for(int j = 0; j < (int)qe[i].size(); ++j)
            A(qe[i][j], -que[qe[i][j]]);
        answer[i] = Calc(tab[i], q);
    }
}

vector<int> distribute_candies(vector<int> _c, vector<int> _l, vector<int> _r, vector<int> _v)
{
    int n = _c.size(), q = _l.size();
    for(int i = 1; i <= n; ++i)
        tab[i] = _c[i - 1];
    que[1] = 2 * II;
    que[2] = -2 * II;
    qb[1].pb(1); qb[1].pb(2);
    for(int i = 3; i <= q + 2; ++i)
    {
        que[i] = _v[i - 3];
        qb[_l[i - 3] + 1].pb(i);
        qe[_r[i - 3] + 2].pb(i);
    }
    q += 2;
    DoA(n, q);
    vector<int> ans;
    for(int i = 1; i <= n; ++i)
        ans.pb(answer[i]);
    return ans;
}

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