Submission #2147307


Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using ll = long long;
using namespace std;

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef typename OperatorMonoid::underlying_type operator_type;
    typedef typename OperatorMonoid::target_type underlying_type;
    int n;
    vector<operator_type> f;
    vector<underlying_type> a;
    const OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n-1, op.unit());
    }
    underlying_type point_get(int i) { // 0-based
        underlying_type acc = a[i];
        for (i = (i+n)/2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i-1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i-n+1] = op.apply(z, a[i-n+1]);
            }
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2*i+1, il, (il+ir)/2, 0, n, f[i]);
            range_apply(2*i+2, (il+ir)/2, ir, 0, n, f[i]);
            f[i] = op.unit();
            range_apply(2*i+1, il, (il+ir)/2, l, r, z);
            range_apply(2*i+2, (il+ir)/2, ir, l, r, z);
        }
    }
};
struct grad_init_operator_monoid {
    typedef tuple<ll, ll, bool, int> underlying_type;  // (a, b, does_erase, set_index), add a * index + b
    typedef pair<ll, int> target_type;  // (value, index)
    underlying_type unit() const {
        return make_tuple(0ll, 0ll, false, -1);
    }
    underlying_type append(underlying_type f, underlying_type g) const {
        if (get<2>(f)) return f;
        ll a = get<0>(f) + get<0>(g);
        ll b = get<1>(f) + get<1>(g);
        bool does_erase = get<2>(g);
        int set_index = max(get<3>(f), get<3>(g));
        return make_tuple(a, b, does_erase, set_index);
    }
    target_type apply(underlying_type f, target_type x) const {
        ll a, b; bool does_erase; int set_index; tie(a, b, does_erase, set_index) = f;
        ll value; int index; tie(value, index) = x;
        ll next_value = a * index + b + (does_erase ? 0 : value);
        int next_index = set_index != -1 ? set_index : index;
        return make_pair(next_value, next_index);
    }
};

template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;  // avoid overflow
        (p(m) ? r : l) = m;
    }
    return r;
}

int main() {
    // input
    int n, l; scanf("%d%d", &n, &l);
    vector<int> t(n), p(n);
    REP (i, n) scanf("%d%d", &t[i], &p[i]);

    // solve
    // // reverse poss to ignore times
    for (int l = 0; l < n; ) {
        int r = l;
        while (r < n and t[l] == t[r]) ++ r;
        reverse(p.begin() + l, p.begin() + r);
        l = r;
    }
    // // compute dp
    dual_segment_tree<grad_init_operator_monoid> dp(l + 1, make_pair(0, -1));
    REP (x, l + 1) {
        dp.range_apply(x, x + 1, make_tuple(0ll, 0ll, false, x));  // init
    }
    for (int p_i : p) {
        dp.range_apply(0, p_i, make_tuple(-1, p_i, false, -1));
        dp.range_apply(p_i, l + 1, make_tuple(1, - p_i, false, -1));
        int x = binsearch(0, l, [&](int x) {
            return dp.point_get(x + 1).first - dp.point_get(x).first >= 0;
        });
        ll min_dp = dp.point_get(x).first;
        dp.range_apply(x, l + 1, make_tuple(0ll, min_dp, true, -1));
    }

    // output
    ll result = dp.point_get(l).first;
    printf("%lld\n", result);
    return 0;
}

Submission Info

Submission Time
Task E - 花火
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 160
Code Size 4040 Byte
Status AC
Exec Time 441 ms
Memory 6144 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:85:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int n, l; scanf("%d%d", &n, &l);
                                    ^
./Main.cpp:87:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     REP (i, n) scanf("%d%d", &t[i], &p[i]);
                                           ^

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 130 / 130
Status
AC × 3
AC × 45
AC × 95
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt, subtask2_47.txt, subtask2_48.txt, subtask2_49.txt, subtask2_50.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 6 ms 384 KB
subtask1_02.txt AC 6 ms 384 KB
subtask1_03.txt AC 6 ms 384 KB
subtask1_04.txt AC 6 ms 384 KB
subtask1_05.txt AC 2 ms 256 KB
subtask1_06.txt AC 2 ms 256 KB
subtask1_07.txt AC 3 ms 256 KB
subtask1_08.txt AC 3 ms 256 KB
subtask1_09.txt AC 6 ms 384 KB
subtask1_10.txt AC 6 ms 384 KB
subtask1_11.txt AC 6 ms 384 KB
subtask1_12.txt AC 6 ms 384 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 2 ms 256 KB
subtask1_15.txt AC 3 ms 256 KB
subtask1_16.txt AC 3 ms 256 KB
subtask1_17.txt AC 6 ms 384 KB
subtask1_18.txt AC 6 ms 384 KB
subtask1_19.txt AC 6 ms 384 KB
subtask1_20.txt AC 6 ms 384 KB
subtask1_21.txt AC 6 ms 384 KB
subtask1_22.txt AC 6 ms 384 KB
subtask1_23.txt AC 6 ms 384 KB
subtask1_24.txt AC 6 ms 384 KB
subtask1_25.txt AC 2 ms 256 KB
subtask1_26.txt AC 3 ms 256 KB
subtask1_27.txt AC 6 ms 384 KB
subtask1_28.txt AC 6 ms 384 KB
subtask1_29.txt AC 1 ms 256 KB
subtask1_30.txt AC 2 ms 256 KB
subtask1_31.txt AC 6 ms 384 KB
subtask1_32.txt AC 6 ms 384 KB
subtask1_33.txt AC 6 ms 384 KB
subtask1_34.txt AC 5 ms 384 KB
subtask1_35.txt AC 5 ms 384 KB
subtask1_36.txt AC 5 ms 384 KB
subtask1_37.txt AC 1 ms 256 KB
subtask1_38.txt AC 2 ms 384 KB
subtask1_39.txt AC 1 ms 256 KB
subtask1_40.txt AC 2 ms 384 KB
subtask1_41.txt AC 1 ms 256 KB
subtask1_42.txt AC 2 ms 384 KB
subtask2_01.txt AC 424 ms 6144 KB
subtask2_02.txt AC 441 ms 6144 KB
subtask2_03.txt AC 428 ms 6144 KB
subtask2_04.txt AC 424 ms 6144 KB
subtask2_05.txt AC 408 ms 6144 KB
subtask2_06.txt AC 324 ms 6016 KB
subtask2_07.txt AC 212 ms 3200 KB
subtask2_08.txt AC 129 ms 3072 KB
subtask2_09.txt AC 22 ms 1024 KB
subtask2_10.txt AC 43 ms 1024 KB
subtask2_11.txt AC 79 ms 1024 KB
subtask2_12.txt AC 118 ms 1024 KB
subtask2_13.txt AC 270 ms 1664 KB
subtask2_14.txt AC 400 ms 6144 KB
subtask2_15.txt AC 407 ms 6144 KB
subtask2_16.txt AC 409 ms 6144 KB
subtask2_17.txt AC 412 ms 6144 KB
subtask2_18.txt AC 406 ms 6144 KB
subtask2_19.txt AC 18 ms 1024 KB
subtask2_20.txt AC 39 ms 1024 KB
subtask2_21.txt AC 74 ms 1024 KB
subtask2_22.txt AC 112 ms 1024 KB
subtask2_23.txt AC 252 ms 1664 KB
subtask2_24.txt AC 409 ms 6144 KB
subtask2_25.txt AC 407 ms 6144 KB
subtask2_26.txt AC 407 ms 6144 KB
subtask2_27.txt AC 413 ms 6144 KB
subtask2_28.txt AC 418 ms 6144 KB
subtask2_29.txt AC 391 ms 6144 KB
subtask2_30.txt AC 402 ms 6144 KB
subtask2_31.txt AC 408 ms 6144 KB
subtask2_32.txt AC 387 ms 6144 KB
subtask2_33.txt AC 414 ms 6144 KB
subtask2_34.txt AC 407 ms 6144 KB
subtask2_35.txt AC 63 ms 1024 KB
subtask2_36.txt AC 97 ms 1024 KB
subtask2_37.txt AC 278 ms 1664 KB
subtask2_38.txt AC 409 ms 6144 KB
subtask2_39.txt AC 404 ms 6144 KB
subtask2_40.txt AC 16 ms 1024 KB
subtask2_41.txt AC 20 ms 1024 KB
subtask2_42.txt AC 403 ms 6144 KB
subtask2_43.txt AC 404 ms 6144 KB
subtask2_44.txt AC 407 ms 6144 KB
subtask2_45.txt AC 305 ms 6144 KB
subtask2_46.txt AC 301 ms 6144 KB
subtask2_47.txt AC 311 ms 6144 KB
subtask2_48.txt AC 45 ms 5376 KB
subtask2_49.txt AC 1 ms 256 KB
subtask2_50.txt AC 45 ms 5376 KB