結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | kimiyuki |
提出日時 | 2019-11-22 01:31:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 428 ms / 3,000 ms |
コード長 | 4,459 bytes |
コンパイル時間 | 2,305 ms |
コンパイル使用メモリ | 209,132 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-10-11 02:28:09 |
合計ジャッジ時間 | 11,590 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 47 ms
5,504 KB |
testcase_03 | AC | 166 ms
12,032 KB |
testcase_04 | AC | 187 ms
5,632 KB |
testcase_05 | AC | 315 ms
12,160 KB |
testcase_06 | AC | 94 ms
7,680 KB |
testcase_07 | AC | 212 ms
12,032 KB |
testcase_08 | AC | 238 ms
7,680 KB |
testcase_09 | AC | 109 ms
12,160 KB |
testcase_10 | AC | 142 ms
7,808 KB |
testcase_11 | AC | 262 ms
12,032 KB |
testcase_12 | AC | 327 ms
12,160 KB |
testcase_13 | AC | 328 ms
12,160 KB |
testcase_14 | AC | 329 ms
12,160 KB |
testcase_15 | AC | 329 ms
12,160 KB |
testcase_16 | AC | 329 ms
12,160 KB |
testcase_17 | AC | 428 ms
12,032 KB |
testcase_18 | AC | 250 ms
12,160 KB |
testcase_19 | AC | 383 ms
12,160 KB |
testcase_20 | AC | 385 ms
12,160 KB |
testcase_21 | AC | 375 ms
12,160 KB |
testcase_22 | AC | 381 ms
12,160 KB |
testcase_23 | AC | 375 ms
12,288 KB |
testcase_24 | AC | 371 ms
12,160 KB |
testcase_25 | AC | 105 ms
5,248 KB |
testcase_26 | AC | 251 ms
12,288 KB |
testcase_27 | AC | 224 ms
12,288 KB |
ソースコード
#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; }