oj.uz

Submission #535781

# Submission time Handle Problem Language Result Execution time Memory
535781 2022-03-11T07:34:59 Z KoD Distributing Candies (IOI21_candies) C++17
29 / 100
 168 ms 19508 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 19508 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 84 ms 6644 KB Output is correct
4 Correct 63 ms 4420 KB Output is correct
5 Correct 168 ms 10756 KB Output is correct
6 Correct 161 ms 14672 KB Output is correct
7 Correct 162 ms 15312 KB Output is correct
8 Correct 160 ms 13880 KB Output is correct
9 Correct 123 ms 15324 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -