Submission #1062766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062766		j_vdd16	Distributing Candies (IOI21_candies)	C++17	0 / 100	1145 ms	49748 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 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
    Entry id = { 0, {LLONG_MAX, 0}, {0, 0}};

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

        tree.resize(2 * N, id);
    }

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

        int 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 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 get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1)
            tr = N;

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

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

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

vi distribute_candies(vi c, vi ls, vi rs, vi 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});
    }

    vi s(n);
    loop(i, n) {
        for (auto [v, idx] : queryStarts[i]) {
            segTree.set(idx, {v, {v, idx}, {v, idx}});
        }
        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.get(m, q + 1);

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

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

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


        for (auto [v, idx] : queryEnds[i]) {
            segTree.set(idx, segTree.id);
        }
    }

    return s;
}

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