Submission #535758

#	Time	Username	Problem	Language	Result	Execution time	Memory
535758		KoD	Distributing Candies (IOI21_candies)	C++17	0 / 100	99 ms	16232 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;

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};
    const auto get = [&](const int i, const int t) {
        const auto [s, x] = map.upper_bound(i)->second;
        return (x == 0 ? 0 : c[i]) + (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) <= c[md]) {
                    ok = md;
                } else {
                    ng = md;
                }
            }
            while (map.begin()->first < ok) {
                map.erase(map.begin());
            }
            std::cerr << ok << std::endl;
            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[i] = get(i, q);
    }
    return ret;
}

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