Submission #435037

#	Time	Username	Problem	Language	Result	Execution time	Memory
435037		VEGAnn	Distributing Candies (IOI21_candies)	C++17	100 / 100	3008 ms	41852 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define l2 array<ll,2>
#define sz(x) ((int)x.size())
#define PB push_back
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int N = 200100;
const ll OO = 1e18;
int n, q;
vector<i2> events[N];
ll psh[4 * N];
l2 mn[N * 4], mx[N * 4];

void pull(int v){
    mn[v] = min(mn[v + v], mn[v + v + 1]);
    mx[v] = max(mx[v + v], mx[v + v + 1]);
}

void build(int v, int l, int r){
    psh[v] = 0;

    if (l == r){
        mn[v] = {0, -l};
        mx[v] = {0, l};
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    pull(v);
}

void push(int v){
    if (psh[v] != 0){
        mn[v][0] += psh[v];
        mx[v][0] += psh[v];

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[v + v + 1] += psh[v];
        }

        psh[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, ll vl){
    push(v);

    if (l > r) return;

    if (tl == l && tr == r){
        psh[v] += vl;

        push(v);

        return;
    }

    int md = (tl + tr) >> 1;

    update(v + v, tl, md, l, min(r, md), vl);
    update(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    pull(v);
}

l2 get_max(int v, int tl, int tr, int l, int r){
    push(v);

    if (l > r) return {-OO, -1};

    if (tl == l && tr == r) return mx[v];

    int md = (tl + tr) >> 1;

    return max(get_max(v + v, tl, md, l, min(r, md)),
               get_max(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

l2 get_min(int v, int tl, int tr, int l, int r){
    push(v);

    if (l > r) return {+OO, -1};

    if (tl == l && tr == r) return mn[v];

    int md = (tl + tr) >> 1;

    return min(get_min(v + v, tl, md, l, min(r, md)),
               get_min(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = sz(c);
    q = sz(l);

    for (int i = 0; i < q; i++){
        events[l[i]].PB({i, +v[i]});
        events[r[i] + 1].PB({i, -v[i]});
    }

    build(1, 0, q);

    vector<int> a;

    a.resize(n);

    for (int i = 0; i < n; i++){
        for (i2 cr : events[i])
            update(1, 0, q, cr[0] + 1, q, cr[1]);

        if (mx[1][0] - mn[1][0] <= c[i]){
            if (mn[1][0] < 0){
                a[i] = get_max(1, 0, q, q, q)[0] - mn[1][0];
            } else {
                a[i] = get_max(1, 0, q, q, q)[0];
            }
        } else {
            int lf = 0, rt = q;

            while (lf < rt){
                int md = (lf + rt + 1) >> 1;

                l2 fi = get_max(1, 0, q, md, q);
                l2 se = get_min(1, 0, q, md, q);

                if (fi[0] - se[0] > c[i])
                    lf = md;
                else rt = md - 1;
            }

            l2 fi = get_max(1, 0, q, lf, q);
            l2 se = get_min(1, 0, q, lf, q);

            if (-fi[1] < se[1]){
                a[i] = ll(c[i]) - (fi[0] - get_max(1, 0, q, q, q)[0]);
            } else {
                a[i] = get_max(1, 0, q, q, q)[0] - se[0];
            }
        }
    }

    return a;
}

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