oj.uz

Submission #563207

# Submission time Handle Problem Language Result Execution time Memory
563207 2022-05-16T13:47:11 Z Cyanmond Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 1 ms 300 KB 
#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.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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