#419418 (C++17) No.973 余興

提出ソース

結果

問題	No.973 余興
ユーザー	kimiyuki
提出日時	2020-01-18 06:10:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,330 bytes
コンパイル時間	2,752 ms
コンパイル使用メモリ	209,496 KB
実行使用メモリ	324,108 KB
最終ジャッジ日時	2023-09-08 18:26:08
合計ジャッジ時間	80,468 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,345 ms 323,768 KB
testcase_01	AC	1,378 ms 323,852 KB
testcase_02	AC	1,369 ms 323,516 KB
testcase_03	AC	1,363 ms 323,500 KB
testcase_04	AC	1,368 ms 323,944 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	1,309 ms 317,284 KB
testcase_11	AC	795 ms 99,372 KB
testcase_12	AC	817 ms 99,372 KB
testcase_13	WA	-
testcase_14	AC	811 ms 99,060 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	24 ms 9,292 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	37 ms 11,476 KB
testcase_23	AC	31 ms 10,400 KB
testcase_24	AC	30 ms 10,476 KB
testcase_25	AC	15 ms 7,816 KB
testcase_26	AC	24 ms 9,308 KB
testcase_27	AC	50 ms 20,588 KB
testcase_28	WA	-
testcase_29	AC	31 ms 10,132 KB
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	AC	2,808 ms 322,984 KB
testcase_35	AC	2,859 ms 324,084 KB
testcase_36	WA	-
testcase_37	WA	-
testcase_38	AC	2,851 ms 323,292 KB
testcase_39	WA	-
testcase_40	AC	2 ms 4,376 KB
testcase_41	AC	1 ms 4,376 KB
testcase_42	AC	1 ms 4,380 KB
testcase_43	WA	-
testcase_44	AC	2 ms 4,380 KB
testcase_45	WA	-
testcase_46	AC	2,865 ms 323,824 KB
testcase_47	WA	-
testcase_48	AC	2,846 ms 323,856 KB
testcase_49	WA	-
testcase_50	AC	2,798 ms 322,536 KB
testcase_51	WA	-
testcase_52	WA	-
testcase_53	AC	2,674 ms 320,816 KB
testcase_54	AC	2,747 ms 323,932 KB
testcase_55	AC	2,712 ms 323,512 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#define dump(x) cerr << #x " = " << x << endl
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <typename X, typename T> auto make_table(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <typename T> istream & operator >> (istream & in, vector<T> & xs) { REP (i, xs.size()) { in >> xs[i]; } return in; }
template <typename T> ostream & operator << (ostream & out, const vector<T> & xs) { REP (i, xs.size()) { if (i) { out << ' '; } out << xs[i]; } return out; }

/**
 * @brief a segment tree / セグメント木
 * @docs data_structure/segment_tree.md
 * @tparam Monoid (commutativity is not required)
 */
template <class Monoid>
struct segment_tree {
    typedef typename Monoid::value_type value_type;
    const Monoid mon;
    int n;
    std::vector<value_type> a;
    segment_tree() = default;
    segment_tree(int n_, const Monoid & mon_ = Monoid()) : mon(mon_) {
        n = 1; while (n < n_) n *= 2;
        a.resize(2 * n - 1, mon.unit());
    }
    void point_set(int i, value_type b) {  // 0-based
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
        for (i = (i + n) / 2; i > 0; i /= 2) {  // 1-based
            a[i - 1] = mon.mult(a[2 * i - 1], a[2 * i]);
        }
    }
    value_type range_get(int l, int r) {  // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        value_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.mult(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.mult(a[(-- r) - 1], racc);
        }
        return mon.mult(lacc, racc);
    }

    value_type point_get(int i) {  // 0-based
        assert (0 <= i and i < n);
        return a[i + n - 1];
    }

    /**
     * @brief a fast & semigroup-friendly version constructor
     * @note $O(n)$
     */
    template <class InputIterator>
    segment_tree(InputIterator first, InputIterator last, const Monoid & mon_ = Monoid()) : mon(mon_) {
        int size = std::distance(first, last);
        n = 1; while (n < size) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        std::copy(first, last, a.begin() + (n - 1));
        unsafe_rebuild();
    }
    /**
     * @brief update a leaf node without updating ancestors
     * @note $O(1)$
     */
    void unsafe_point_set(int i, value_type b) {  // 0-based
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
    }
    /**
     * @brief re-build non-leaf nodes from leaf nodes
     * @note $O(n)$
     */
    void unsafe_rebuild() {
        REP_R (i, n - 1) {
            a[i] = mon.mult(a[2 * i + 1], a[2 * i + 2]);
        }
    }
};

template <class T>
struct plus_monoid {
    typedef T value_type;
    value_type unit() const { return value_type(); }
    value_type mult(value_type a, value_type b) const { return a + b; }
};

/**
 * @brief a binary search / 二分探索
 * @param[in] p  a monotone predicate defined on $[l, r)$
 * @return $\min \lbrace x \in [l, r) \mid p(x) \rbrace$, or r if it doesn't exist
 */
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;
        (p(m) ? r : l) = m;
    }
    return r;
}

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


bool solve(int n, int x, const vector<int64_t> & a) {
    vector<int64_t> acc(n + 1);
    partial_sum(ALL(a), acc.begin() + 1);
    auto hr = make_table(n + 1, segment_tree<plus_monoid<int16_t> >(n + 1));
    auto vr = make_table(n + 1, segment_tree<plus_monoid<int16_t> >(n + 1));
    REP (len, n + 1) REP (l, n - len + 1) {
        int r = l + len;
        bool cur;
        if (len == 0) {
            cur = false;
        } else {
            int m1 = binsearch(l + 1, r + 1, [&](int m1) {
                return acc[m1] - acc[l] > x;
            });
            int m2 = binsearch(l, r, [&](int m2) {
                return acc[r] - acc[m2] <= x;
            });
            cur = hr[l].range_get(l + 1, m1) or vr[r].range_get(m2, r);
        }
        if (not cur) {
            hr[l].point_set(r, 1);
            vr[r].point_set(l, 1);
        }
    }
    return not hr[0].point_get(n);
}

int main() {
    int n, x; cin >> n >> x;
    vector<int64_t> a(n); cin >> a;
    cout << (solve(n, x, a) ? "A" : "B") << endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード