oj.uz

Submission #558845

# Submission time Handle Problem Language Result Execution time Memory
558845 2022-05-08T18:14:57 Z teraqqq Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 62488 KB 
#include "candies.h"

#include <iostream>
#include <vector>

using namespace std;
using vi = vector<int>;
using ll = long long;

const ll LINF = 1e18;

struct SegmentTreeMin {
    int n;
    vector<pair<ll, int>> tmin;
    vector<ll> tadd;

    SegmentTreeMin(int n, const vector<int>& w) : n(n), tmin(4*n), tadd(4*n) {
        build(w);
    }

    void build(int v, int vl, int vr, const vector<int>& w) {
        tadd[v] = 0;

        if (vl + 1 == vr) {
            tmin[v] = { w[vl], vl };
        } else {
            int vm = (vl + vr) / 2;
            build(2*v, vl, vm, w);
            build(2*v+1, vm, vr, w);
            tmin[v] = min(tmin[2*v], tmin[2*v+1]);
        }
    }

    void build(const vector<int>& w) {
        build(1, 0, n, w);
    }

    void add(int v, int vl, int vr, int l, int r, ll x) {
        if (l <= vl && vr <= r) {
            tadd[v]       += x;
            tmin[v].first += x;
        } else if (r <= vl || vr <= l) {
            /* nope :D */
        } else {
            int vm = (vl + vr) / 2;
            add(2*v,   vl, vm, l, r, x);
            add(2*v+1, vm, vr, l, r, x);
            tmin[v] = min(tmin[2*v], tmin[2*v+1]);
            tmin[v].first += tadd[v];
        }
    }

    void add(int l, int r, ll x) {
        add(1, 0, n, l, r, x);
    }

    pair<ll, int> query(int v, int vl, int vr, int l, int r) {
        if (l <= vl && vr <= r) return tmin[v];
        if (r <= vl || vr <= l) return { LINF, -1 };

        int vm = (vl + vr) / 2;
        auto res = min(query(2*v, vl, vm, l, r), query(2*v+1, vm, vr, l, r));
        res.first += tadd[v];
        return res;
    }

    pair<ll, int> query(int l, int r) {
        return query(1, 0, n, l, r);
    }
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
    const int n = c.size(), q = v.size();

    for (int& x : r) ++x;

    vector<int> ans_l(n), ans_r(n);
    for (int i = n; i--; ) ans_r[i] = c[i] + 1;

    for (int iter = 30; iter--; ) {
        vector<int> wlb(n), wrb(n);
        for (int i = n; i--; ) {
            wlb[i] = (ans_l[i] + ans_r[i]) / 2;
            wrb[i] = c[i] - wlb[i];
        }

        SegmentTreeMin sgt_lb(n, wlb), sgt_ub(n, wrb);
        vector<int> lb_out(n, -1), ub_out(n, -1);
        vector<ll> lb_outx(n, -1), ub_outx(n, -1);

        vector<int> lb_outh(n, -1), ub_outh(n, -1);
        vector<ll> lb_outxh(n, -1), ub_outxh(n, -1);

        for (int j = q; j >= 0; j--) {
            if (j != q) {
                sgt_lb.add(l[j], r[j], -v[j]);
                sgt_ub.add(l[j], r[j], +v[j]);
            }

            while (true) {
                const auto [val, i] = sgt_lb.query(0, n);
                if (val > 0) break;
                lb_outx[i] = val;
                lb_out[i] = j;
                sgt_lb.add(i, i+1, LINF);
            }

            while (true) {
                const auto [val, i] = sgt_ub.query(0, n);
                if (val > 0) break;
                ub_outx[i] = val;
                ub_out[i] = j;
                sgt_ub.add(i, i+1, LINF);
            }
        }

        sgt_ub.build(wrb);

        for (int j = q; j >= 0; j--) {
            if (j != q) {
                sgt_ub.add(l[j], r[j], +v[j]);
            }

            while (true) {
                const auto [val, i] = sgt_ub.query(0, n);
                if (val >= 0) break;
                ub_outxh[i] = val;
                ub_outh[i] = j;
                sgt_ub.add(i, i+1, LINF);
            }
        }

        vector<int> hard_case(n);

        for (int i = 0; i < n; ++i) {
            if (lb_out[i] == -1 && ub_out[i] == -1) {
                ans_r[i] = wlb[i];
            } else {
                if (lb_out[i] > ub_out[i]) {
                    ans_l[i] = wlb[i];
                } else {
                    if (ub_outx[i] == 0) {
                        if (lb_out[i] > ub_outh[i]) {
                            ans_l[i] = wlb[i];
                        } else {
                            ans_r[i] = wlb[i];
                        }
                    } else {
                        ans_r[i] = wlb[i];
                    }
                }
            }
        }
    }

    return ans_l;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 13 ms 364 KB Output is correct
4 Correct 33 ms 312 KB Output is correct
5 Correct 101 ms 888 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 62488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 564 KB Output is correct
2 Execution timed out 5051 ms 8756 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 17 ms 556 KB Output is correct
3 Correct 190 ms 8228 KB Output is correct
4 Execution timed out 5044 ms 54304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 13 ms 364 KB Output is correct
4 Correct 33 ms 312 KB Output is correct
5 Correct 101 ms 888 KB Output is correct
6 Execution timed out 5030 ms 62488 KB Time limit exceeded
7 Halted 0 ms 0 KB -