oj.uz

Submission #535761

# Submission time Handle Problem Language Result Execution time Memory
535761 2022-03-11T06:47:13 Z KoD Distributing Candies (IOI21_candies) C++17
0 / 100
 82 ms 16356 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};
    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());
            }
            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.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 82 ms 16356 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
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 -