Submission #1062981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062981		j_vdd16	Distributing Candies (IOI21_candies)	C++17	100 / 100	2276 ms	58556 KiB

candies

#include "candies.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define ll long long
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef tuple<ll, pair<ll, int>, pair<ll, int>> Entry;

struct SegTree {
    int n = -1, N = -1;
    vector<Entry> tree; //sum, min, max
    vector<ll> lazy;
    Entry id = { 0, {LLONG_MAX / 2, 0}, {LLONG_MIN / 2, 0}};

    SegTree(int _n) {
        n = _n;
        N = 1;
        while (N < n) N *= 2;

        tree.resize(2 * N);
        loop(i, n) {
            tree[N + i] = { 0, { 0, i}, { 0, i }};
        }
        for (int i = N - 1; i >= 1; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }

        lazy.resize(2 * N, 0);
        //sums = SumTree(n);
    }

    Entry merge(Entry a, Entry b) {
        auto [s1, min1, max1] = a;
        auto [s2, min2, max2] = b;

        ll s = s1 + s2;
        ii mn;
        if (min1.first < min2.first) {
            mn.first = min1.first;
            mn.second = min1.second;
        }
        else {
            mn.first = min2.first;
            mn.second = min2.second;
        }

        ii mx;
        if (max1.first > max2.first) {
            mx.first = max1.first;
            mx.second = max1.second;
        }
        else {
            mx.first = max2.first;
            mx.second = max2.second;
        }

        return {s, mn, mx};
    }

    void add2(int idx, ll v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;
 
        if (tr - tl == 1) {
            get<0>(tree[i]) += v;
            return;
        }
 
        int tm = (tl + tr) / 2;
        if (idx < tm) {
            add2(idx, v, 2 * i, tl, tm);
        }
        else {
            add2(idx, v, 2 * i + 1, tm, tr);
        }
 
        get<0>(tree[i]) = get<0>(tree[2 * i]) + get<0>(tree[2 * i + 1]);
    }
    void add(int l, int r, ll v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;

        if (lazy[i]) {
            get<1>(tree[i]).first += lazy[i];
            get<2>(tree[i]).first += lazy[i];

            if (tr - tl > 1) {
                lazy[2 * i] += lazy[i];
                lazy[2 * i + 1] += lazy[i];
            }
            lazy[i] = 0;
        }

        if (l >= tr || r <= tl) {
            return;
        }
        if (tl >= l && tr <= r) {
            get<1>(tree[i]).first += v;
            get<2>(tree[i]).first += v;

            if (tr - tl > 1) {
                lazy[2 * i] += v;
                lazy[2 * i + 1] += v;
            }

            return;
        }

        int tm = (tl + tr) / 2;
        if (l < tm) {
            add(l, r, v, 2 * i, tl, tm);
            add(l, r, v, 2 * i + 1, tm, tr);
        }
        else {
            add(l, r, 0, 2 * i, tl, tm);
            add(l, r, v, 2 * i + 1, tm, tr);
        }

        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
    
    void set(int idx, const Entry& v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;

        if (tr - tl == 1) {
            tree[i] = v;
            return;
        }

        int tm = (tl + tr) / 2;
        if (idx < tm) {
            set(idx, v, 2 * i, tl, tm);
        }
        else {
            set(idx, v, 2 * i + 1, tm, tr);
        }

        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }

    Entry getRange(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;

        if (lazy[i]) {
            get<1>(tree[i]).first += lazy[i];
            get<2>(tree[i]).first += lazy[i];

            if (tr - tl > 1) {
                lazy[2 * i] += lazy[i];
                lazy[2 * i + 1] += lazy[i];
            }
            lazy[i] = 0;
        }

        if (l >= tr || r <= tl)
            return id;

        if (tl >= l && tr <= r)
            return tree[i];

        int tm = (tl + tr) / 2;
        return merge(getRange(l, r, 2 * i, tl, tm), getRange(l, r, 2 * i + 1, tm, tr));
    }
};

vector<signed> distribute_candies(vector<signed> c, vector<signed> ls, vector<signed> rs, vector<signed> vs) {
    int n = c.size();
    int q = ls.size();

    SegTree segTree(q + 1);
    vvii queryStarts(n), queryEnds(n);
    loop(i, q) {
        int l = ls[i];
        int r = rs[i];
        int v = vs[i];

        queryStarts[l].push_back({v, i + 1});
        queryEnds[r].push_back({v, i + 1});
    }

    vector<signed> s(n);
    loop(i, n) {
        for (auto [v, idx] : queryStarts[i]) {
            segTree.add(idx, q + 1, v);
            segTree.add2(idx, v);
        }
        segTree.set(0, {0, {0, 0}, {c[i], 0}});

        int l = 0, r = q;
        while (l < r) {
            int m = (l + r + 1) / 2;

            //ll diff = sufMax[m].first - sufMin[m].first;
            auto [sum, mn, mx] = segTree.getRange(m, q + 1);

            ll diff = mx.first - mn.first;
            if (diff < (ll)c[i]) {
                r = m - 1;
            }
            else { 
                l = m;
            }
        }

        auto [sum, mn, mx] = segTree.getRange(l, q + 1);
        if (l == 0 && mx.first - mn.first <= (ll)c[i]) {
            //s[i] = cumul.back();
            ll extra = get<0>(segTree.getRange(0, q + 1));
            s[i] = extra;
        }
        else {
            //int lastMin = sufMin[l].second;
            //int lastMax = sufMax[l].second;
            int lastMin = mn.second;
            int lastMax = mx.second;

            ll value = 0;
            if (lastMin >= lastMax) {
                l = lastMin;
            }
            else {
                l = lastMax;
                value = c[i];
            }

            //s[i] += cumul.back() - cumul[l];
            ll extra = get<0>(segTree.getRange(l + 1, q + 1));
            s[i] = value + extra;
        }

        for (auto [v, idx] : queryEnds[i]) {
            segTree.add(idx, q + 1, -v);
            segTree.add2(idx, -v);
        }
    }

    return s;
}

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