Submission #535781

#	Time	Username	Problem	Language	Result	Execution time	Memory
535781		KoD	Distributing Candies (IOI21_candies)	C++17	29 / 100	168 ms	19508 KiB

candies

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

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

struct Fenwick {
    vector<ll> data;
    explicit Fenwick(const int n) : data(n + 1) {}

    void add(int i, const ll x) {
        i += 1;
        while (i < (int)data.size()) {
            data[i] += x;
            i += i & -i;
        }
    }

    ll pref(int i) const {
        ll ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }

    ll fold(const int l, const int r) const {
        return pref(r) - pref(l);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    const int n = c.size();
    const int q = v.size();
    vector<ll> sum(q + 1);
    std::map<int, pair<int, int>> map;
    map[n] = {0, 0};
    vector<pair<int, int>> sort(n);
    for (int i = 0; i < n; ++i) {
        sort[i] = {c[i], i};
    }
    std::sort(sort.begin(), sort.end());
    const auto get = [&](const int i, const int t) {
        const auto [s, x] = map.upper_bound(i)->second;
        return (x == 0 ? 0 : sort[i].first) + (sum[t] - sum[s]);
    };
    for (int i = 0; i < q; ++i) {
        assert(l[i] == 0 and r[i] == n - 1);
        sum[i + 1] = sum[i] + v[i];
        if (v[i] > 0) {
            int ok = n, ng = -1;
            while (ok - ng > 1) {
                const int md = (ok + ng) / 2;
                if (get(md, i + 1) <= sort[md].first) {
                    ok = md;
                } else {
                    ng = md;
                }
            }
            while (map.begin()->first < ok) {
                map.erase(map.begin());
            }
            map[ok] = {i + 1, 1};
        } else {
            int ok = n, ng = -1;
            while (ok - ng > 1) {
                const int md = (ok + ng) / 2;
                if (get(md, i + 1) >= 0) {
                    ok = md;
                } else {
                    ng = md;
                }
            }
            while (map.begin()->first < ok) {
                map.erase(map.begin());
            }
            map[ok] = {i + 1, 0};
        }
    }
    vector<int> ret(n);
    for (int i = 0; i < n; ++i) {
        ret[sort[i].second] = get(i, q);
    }
    return ret;
}

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