結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | nebukuro09 |
提出日時 | 2018-12-25 06:35:05 |
言語 | D (dmd 2.107.1) |
結果 |
AC
|
実行時間 | 742 ms / 3,000 ms |
コード長 | 3,000 bytes |
コンパイル時間 | 809 ms |
コンパイル使用メモリ | 109,248 KB |
実行使用メモリ | 24,680 KB |
最終ジャッジ日時 | 2023-09-03 21:46:03 |
合計ジャッジ時間 | 16,986 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 68 ms
7,236 KB |
testcase_03 | AC | 265 ms
15,216 KB |
testcase_04 | AC | 297 ms
8,060 KB |
testcase_05 | AC | 524 ms
15,680 KB |
testcase_06 | AC | 151 ms
9,480 KB |
testcase_07 | AC | 348 ms
20,104 KB |
testcase_08 | AC | 392 ms
9,852 KB |
testcase_09 | AC | 173 ms
15,788 KB |
testcase_10 | AC | 231 ms
9,704 KB |
testcase_11 | AC | 435 ms
16,380 KB |
testcase_12 | AC | 546 ms
17,536 KB |
testcase_13 | AC | 550 ms
15,572 KB |
testcase_14 | AC | 549 ms
24,680 KB |
testcase_15 | AC | 553 ms
15,548 KB |
testcase_16 | AC | 551 ms
16,372 KB |
testcase_17 | AC | 742 ms
16,092 KB |
testcase_18 | AC | 402 ms
15,684 KB |
testcase_19 | AC | 609 ms
15,196 KB |
testcase_20 | AC | 614 ms
22,320 KB |
testcase_21 | AC | 605 ms
15,396 KB |
testcase_22 | AC | 627 ms
15,916 KB |
testcase_23 | AC | 644 ms
16,460 KB |
testcase_24 | AC | 619 ms
15,676 KB |
testcase_25 | AC | 84 ms
7,736 KB |
testcase_26 | AC | 409 ms
15,440 KB |
testcase_27 | AC | 359 ms
19,492 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, lmax, rmax, 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; } } }