結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | nebukuro09 |
提出日時 | 2018-12-29 19:12:29 |
言語 | D (dmd 2.107.1) |
結果 |
AC
|
実行時間 | 723 ms / 3,000 ms |
コード長 | 2,987 bytes |
コンパイル時間 | 3,304 ms |
コンパイル使用メモリ | 108,476 KB |
実行使用メモリ | 27,240 KB |
最終ジャッジ日時 | 2023-09-03 21:47:15 |
合計ジャッジ時間 | 15,146 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 67 ms
6,856 KB |
testcase_03 | AC | 258 ms
15,696 KB |
testcase_04 | AC | 291 ms
6,948 KB |
testcase_05 | AC | 518 ms
15,316 KB |
testcase_06 | AC | 148 ms
10,748 KB |
testcase_07 | AC | 343 ms
15,036 KB |
testcase_08 | AC | 385 ms
12,164 KB |
testcase_09 | AC | 170 ms
15,996 KB |
testcase_10 | AC | 227 ms
9,912 KB |
testcase_11 | AC | 426 ms
16,892 KB |
testcase_12 | AC | 538 ms
16,476 KB |
testcase_13 | AC | 540 ms
19,828 KB |
testcase_14 | AC | 543 ms
20,496 KB |
testcase_15 | AC | 542 ms
16,376 KB |
testcase_16 | AC | 536 ms
16,300 KB |
testcase_17 | AC | 723 ms
17,312 KB |
testcase_18 | AC | 390 ms
24,640 KB |
testcase_19 | AC | 608 ms
15,760 KB |
testcase_20 | AC | 622 ms
17,528 KB |
testcase_21 | AC | 617 ms
15,348 KB |
testcase_22 | AC | 621 ms
15,448 KB |
testcase_23 | AC | 631 ms
27,240 KB |
testcase_24 | AC | 609 ms
15,224 KB |
testcase_25 | AC | 84 ms
7,768 KB |
testcase_26 | AC | 400 ms
16,300 KB |
testcase_27 | AC | 346 ms
22,020 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, core.stdc.string; immutable long MOD = 10^^9 + 7; immutable long INF = 1L << 59; alias Node = Tuple!(long, "sum", long, "lmax", long, "rmax", long, "allmax"); Node merge(Node l, Node r) { long lmax = max(l.lmax, l.sum + r.lmax); long rmax = max(r.rmax, r.sum + l.rmax); long allmax = max(l.allmax, r.allmax, l.rmax + r.lmax); return Node(l.sum + r.sum, lmax, rmax, allmax); } class SegmentTree(T, alias op, T e) { T[] table; int size; int offset; this(int n) { size = 1; while (size <= n) size <<= 1; size <<= 1; table = new T[](size); fill(table, e); offset = size / 2; } void assign(int pos, T val) { pos += offset; table[pos] = val; while (pos > 1) { pos /= 2; table[pos] = op(table[pos*2], table[pos*2+1]); } } T query(int l, int r) { if (r < l) return e; return query(l, r, 1, 0, offset-1); } T query(int l, int r, int i, int a, int b) { if (b < l || r < a) { return e; } else if (l <= a && b <= r) { return table[i]; } else { return op(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b)); } } } void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto Q = s[1]; auto A = readln.split.map!(to!long).array; auto st = new SegmentTree!(Node, merge, Node(0L, -INF, -INF, -INF))(N); foreach (i; 0..N) st.assign(i, Node(A[i], A[i], A[i], A[i])); while (Q--) { auto q = readln.split; if (q[0] == "set") { auto i = q[1].to!int - 1; auto x = q[2].to!long; st.assign(i, Node(x, x, x, x)); } else { auto l1 = q[1].to!int - 1; auto l2 = q[2].to!int - 1; auto r1 = q[3].to!int - 1; auto r2 = q[4].to!int - 1; l2 = min(l2, r2); r1 = max(l1, r1); long ans = -INF; if (l2 < r1) { auto v1 = st.query(l1, l2).rmax; auto v2 = st.query(l2+1, r1-1).sum; auto v3 = st.query(r1, r2).lmax; ans = v1 + v2 + v3; } else { if (l1 < r1) { auto v1 = st.query(l1, r1-1).rmax; auto v2 = st.query(r1, r2).lmax; ans = max(ans, v1 + v2); } if (l2 < r2) { auto v1 = st.query(l1, l2).rmax; auto v2 = st.query(l2+1, r2).lmax; ans = max(ans, v1 + v2); } auto hoge = st.query(r1, l2); ans = max(ans, st.query(r1, l2).allmax); } ans.writeln; } } }