結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | nebukuro09 |
提出日時 | 2018-12-25 06:35:05 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 770 ms / 3,000 ms |
コード長 | 3,000 bytes |
コンパイル時間 | 1,026 ms |
コンパイル使用メモリ | 123,520 KB |
実行使用メモリ | 22,876 KB |
最終ジャッジ日時 | 2024-06-13 02:25:24 |
合計ジャッジ時間 | 17,761 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 99 ms
6,400 KB |
testcase_03 | AC | 308 ms
14,068 KB |
testcase_04 | AC | 317 ms
7,436 KB |
testcase_05 | AC | 546 ms
14,112 KB |
testcase_06 | AC | 161 ms
8,508 KB |
testcase_07 | AC | 371 ms
18,900 KB |
testcase_08 | AC | 405 ms
8,688 KB |
testcase_09 | AC | 187 ms
14,588 KB |
testcase_10 | AC | 241 ms
8,856 KB |
testcase_11 | AC | 485 ms
14,636 KB |
testcase_12 | AC | 592 ms
15,964 KB |
testcase_13 | AC | 589 ms
14,940 KB |
testcase_14 | AC | 586 ms
22,876 KB |
testcase_15 | AC | 577 ms
14,936 KB |
testcase_16 | AC | 575 ms
14,936 KB |
testcase_17 | AC | 770 ms
14,812 KB |
testcase_18 | AC | 433 ms
15,560 KB |
testcase_19 | AC | 646 ms
14,768 KB |
testcase_20 | AC | 651 ms
20,988 KB |
testcase_21 | AC | 641 ms
14,760 KB |
testcase_22 | AC | 646 ms
14,948 KB |
testcase_23 | AC | 672 ms
14,804 KB |
testcase_24 | AC | 653 ms
14,700 KB |
testcase_25 | AC | 83 ms
7,296 KB |
testcase_26 | AC | 432 ms
14,812 KB |
testcase_27 | AC | 381 ms
17,504 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; } } }