Submission #563207

#	Time	Username	Problem	Language	Result	Execution time	Memory
563207		Cyanmond	Bali Sculptures (APIO15_sculpture)	C++17	0 / 100	1 ms	300 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr int inf = 1 << 25;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()

template <class M> class DualSegTree {
    int n, size;
    using T = typename M::T;
    vector<T> data;

  public:
    DualSegTree(int n_) : n(n_) {
        size = 1;
        while (size < n) size <<= 1;
        data.assign(2 * size, M::id());
    }

    void set(int i, const T v) {
        i += size;
        data[i] = M::op(data[i], v);
    }

    void apply(int l, int r, const T v) {
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                data[l] = M::op(data[l], v);
                ++l;
            }
            if (r & 1) {
                --r;
                data[r] = M::op(data[r], v);
            }
        }
    }

    T get(int i) {
        i += size;
        T res = M::id();
        while (i != 0) {
            res = M::op(res, data[i]);
            i >>= 1;
        }
        return res;
    }
};

struct RCMin {
    using T = int;
    static int op(int a, int b) { return min(a, b); }
    static int id() { return inf; }
};
struct RCMax {
    using T = int;
    static int op(int a, int b) { return max(a, b); }
    static int id() { return -inf; }
};

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    ++B;
    vector<i64> Y(N);
    for (auto &e : Y) cin >> e;
    vector<i64> Yc(N + 1);
    REP(i, N) Yc[i + 1] = Yc[i] + Y[i];

    i64 ans = 0;
    RVP(b, 50) {
        const i64 l = ans, r = ans + (1ll << b);
        DualSegTree<RCMin> dpmin(N + 1);
        DualSegTree<RCMax> dpmax(N + 1);
        dpmin.set(0, 0);
        dpmax.set(0, 0);
        REP(i, N) {
            const int t_l = lower_bound(ALL(Yc), Yc[i] + l) - Yc.begin();
            const int t_r = lower_bound(ALL(Yc), Yc[i] + r) - Yc.begin();
            dpmin.apply(t_l, t_r, dpmin.get(i) + 1);
            dpmax.apply(t_l, t_r, dpmax.get(i) + 1);
        }
        const int k_l = dpmin.get(N), k_r = dpmax.get(N) + 1;
        if (max(A, k_l) < min(B, k_r)) {
            ans = l;
        } else {
            ans = r;
        }
    }
    cout << ans << endl;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29