結果

問題 No.776 A Simple RMQ Problem
ユーザー kimiyukikimiyuki
提出日時 2019-11-22 01:31:58
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 412 ms / 3,000 ms
コード長 4,459 bytes
コンパイル時間 2,246 ms
コンパイル使用メモリ 203,252 KB
実行使用メモリ 12,304 KB
最終ジャッジ日時 2024-04-19 10:07:39
合計ジャッジ時間 10,909 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 41 ms
6,944 KB
testcase_03 AC 151 ms
12,008 KB
testcase_04 AC 175 ms
6,940 KB
testcase_05 AC 284 ms
12,076 KB
testcase_06 AC 88 ms
7,552 KB
testcase_07 AC 197 ms
12,020 KB
testcase_08 AC 223 ms
7,480 KB
testcase_09 AC 99 ms
12,160 KB
testcase_10 AC 135 ms
7,580 KB
testcase_11 AC 237 ms
12,148 KB
testcase_12 AC 296 ms
12,272 KB
testcase_13 AC 296 ms
12,188 KB
testcase_14 AC 298 ms
12,292 KB
testcase_15 AC 298 ms
12,172 KB
testcase_16 AC 302 ms
12,164 KB
testcase_17 AC 412 ms
12,160 KB
testcase_18 AC 222 ms
12,304 KB
testcase_19 AC 352 ms
12,232 KB
testcase_20 AC 342 ms
12,244 KB
testcase_21 AC 352 ms
12,132 KB
testcase_22 AC 352 ms
12,172 KB
testcase_23 AC 346 ms
12,276 KB
testcase_24 AC 339 ms
12,260 KB
testcase_25 AC 92 ms
6,944 KB
testcase_26 AC 215 ms
12,184 KB
testcase_27 AC 189 ms
12,164 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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)
using namespace std;

/**
 * @brief a segment tree
 * @tparam Monoid (commutativity is not required)
 */
template <class Monoid>
struct segment_tree {
    typedef typename Monoid::value_type value_type;
    int n;
    std::vector<value_type> a;
    const Monoid mon;
    segment_tree() = default;
    segment_tree(int a_n, value_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid()) : mon(a_mon) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        std::fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
        REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
    }
    void point_set(int i, value_type z) { // 0-based
        assert (0 <= i and i <= n);
        a[i + n - 1] = z;
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            a[i - 1] = mon.append(a[2 * i - 1], a[2 * i]);
        }
    }
    value_type range_concat(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.append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
        }
        return mon.append(lacc, racc);
    }
};

struct subinterval_max_sum_monoid {
    typedef struct {
        int64_t left, sum, right, max;
    } value_type;
    value_type unit() const {
        return (value_type) { 0ll, 0ll, 0ll, INT64_MIN };
    }
    value_type append(value_type a, value_type b) const {
        if (a.max == INT64_MIN) return b;
        if (b.max == INT64_MIN) return a;
        int64_t left = max(a.left, a.sum + b.left);
        int64_t sum = a.sum + b.sum;
        int64_t right = max(a.right + b.sum, b.right);
        int64_t max_ = max(left, max(sum, max(right, max(a.right + b.left, max(a.max, b.max)))));
        return (value_type) { left, sum, right, max_  };
    }
    static value_type make(int64_t a) {
        return (value_type) { a, a, a, a };
    }
    template <class SegmentTree>
    static int64_t calculate(SegmentTree & segtree, int l1, int l2, int r1, int r2) {
        // use [l, r] for l in [l1, l2) and r in [r1, r2)
        assert (l1 <= l2);  // [l1, l2)
        assert (r1 <= r2);  // [r1, r2)
        r1 = max(r1, l1);
        r2 = max(r2, l1);
        l1 = min(l1, r2);
        l2 = min(l2, r2);
        assert (l1 <= r1 and r1 <= r2);
        assert (l1 <= l2 and l2 <= r2);
        int64_t answer = INT64_MIN;
        if (r1 < l2) {
            answer = max(answer, segtree.range_concat(r1, l2).max);
            if (l1 <= r1 and r1 <= l2) {
                answer = max(answer, segtree.range_concat(l1, r1).right + segtree.range_concat(r1, min(l2, r2)).left);
            }
            if (r1 <= l2 and l2 <= r2) {
                answer = max(answer, segtree.range_concat(max(l1, r1), l2).right + segtree.range_concat(l2, r2).left);
            }
            swap(l2, r1);
        }
        answer = max(answer, segtree.range_concat(l1, l2).right + segtree.range_concat(l2, r1).sum + segtree.range_concat(r1, r2).left);
        return answer;
    }
};

int main() {
    // read the initial sequence
    int n, q; cin >> n >> q;
    vector<int64_t> a(n);
    REP (i, n) {
        cin >> a[i];
    }

    // construct a segment tree
    segment_tree<subinterval_max_sum_monoid> segtree(n);
    REP (i, n) {
        segtree.point_set(i, subinterval_max_sum_monoid::make(a[i]));
    }

    // handle queries
    while (q --) {
        string cmd; cin >> cmd;

        if (cmd == "set") {
            int i; int64_t x; cin >> i >> x;
            -- i;
            segtree.point_set(i, subinterval_max_sum_monoid::make(x));

        } else if (cmd == "max") {
            int l1, l2, r1, r2; cin >> l1 >> l2 >> r1 >> r2;  // [l1, l2], [r1, r2]
            -- l1;
            -- r1;
            cout << subinterval_max_sum_monoid::calculate<>(segtree, l1, l2, r1, r2) << endl;
        }
    }

    return 0;
}
0