結果
問題 | No.789 範囲の合計 |
ユーザー | InTheBloom |
提出日時 | 2024-04-30 03:48:09 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 173 ms / 1,000 ms |
コード長 | 6,142 bytes |
コンパイル時間 | 4,922 ms |
コンパイル使用メモリ | 228,096 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-04-30 03:48:17 |
合計ジャッジ時間 | 7,379 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 165 ms
5,504 KB |
testcase_03 | AC | 155 ms
5,376 KB |
testcase_04 | AC | 173 ms
5,760 KB |
testcase_05 | AC | 152 ms
5,376 KB |
testcase_06 | AC | 156 ms
5,376 KB |
testcase_07 | AC | 130 ms
5,376 KB |
testcase_08 | AC | 150 ms
5,760 KB |
testcase_09 | AC | 137 ms
5,760 KB |
testcase_10 | AC | 161 ms
5,376 KB |
testcase_11 | AC | 127 ms
5,632 KB |
testcase_12 | AC | 124 ms
5,632 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
ソースコード
void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } } void main () { // yosupojudge_Point_Add_Range_Sum(); yukicoder_789(); } void yosupojudge_Point_Add_Range_Sum () { import std; // yosupo judge: Point Add Range Sum (https://judge.yosupo.jp/problem/point_add_range_sum) long len = 10^^9; auto seg = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(len); int N, Q; readln.read(N, Q); auto a = readln.split.to!(int[]); foreach (i; 0..N) seg.set(i, a[i]); // seg.dump(); // writeln(); foreach (i; 0..Q) { int t, l, r; readln.read(t, l, r); if (t == 0) { seg.set(l, seg.get(l) + r); // seg.dump(); // writeln(); } if (t == 1) { writeln(seg.prod(l, r)); } } } void yukicoder_789 () { import std; // yukicoder No.789 範囲の合計 long len = 10^^9; auto seg = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(len); int N = readln.chomp.to!int; long ans = 0; foreach (i; 0..N) { int t, l, r; readln.read(t, l, r); if (t == 0) { seg.set(l, seg.get(l) + r); // seg.dump(); // writeln(); } if (t == 1) { ans += seg.prod(l, r + 1); } } writeln(ans); } import std.traits : ReturnType, isCallable, Parameters; import std.meta : AliasSeq; class DynamicSegmentTree (T, alias op, alias e) { // TODO: assertのメッセージを表示 static assert(isCallable!(op)); static assert(isCallable!(e)); static assert(is (ReturnType!(op) == T)); static assert(is (ReturnType!(e) == T)); static assert(is (Parameters!(op) == AliasSeq!(T, T))); static assert(is (Parameters!(e) == AliasSeq!())); // 内部が1-indexedで動的な完全二分セグメント木 import std.format : format; public: this (long N_) in { assert(1 <= N_, format("Dynamic SegmentTree: N = %s does not satisfy constraints. N must be in range of [1, %s]", 4 * 10L^^18)); } do { length = N_; // N_以上の2冪に設定 if ((N_ & (-N_)) == N_) { N = N_; } else { // msb+1 bitを立てる foreach_reverse (i; 0..63) { if (0 < (N_ & (1L << i))) { N = 1L << (i + 1); break; } } } } void set (long idx, T val) { idx++; internal_set(root, idx, val, 1, N + 1); } T get (long idx) { idx++; return internal_get(root, idx, 1, N + 1); } T prod (long l, long r) { l++, r++; return internal_prod(root, l, r, 1, N + 1); } void dump () { dfs(root); } private: struct node { long index; T value, product; int left = -1, right = -1; } void node_update (int cur) { pool[cur].product = op( op((pool[cur].left == -1 ? e() : pool[pool[cur].left].product), pool[cur].value), (pool[cur].right == -1 ? e() : pool[pool[cur].right].product) ); } import std.container : Array; auto pool = Array!(node)(); int root = -1; long N = 0; long length = 0; void dfs (const int cur) { if (cur == -1) return; import std.stdio; writeln("index: ", pool[cur].index - 1, " value: ", pool[cur].value, " product: ", pool[cur].product); dfs(pool[cur].left); dfs(pool[cur].right); } // [l, r) : 今見ている部分木が管理する範囲 int internal_set (int cur, long idx, T val, long l, long r) { if (cur == -1) { pool ~= node(idx, val, val, -1, -1); if (root == -1) return root = 0; return cast(int) (pool.length) - 1; } if (pool[cur].index == idx) { pool[cur].value = val; node_update(cur); return cur; } // 既に部分木管理ノードが存在するときの処理 import std.algorithm : swap; long mid = (l + r) / 2; if (idx < mid) { // 今いる人を押しのける if (pool[cur].index < idx) { swap(pool[cur].value, val); swap(pool[cur].index, idx); } auto v = internal_set(pool[cur].left, idx, val, l, mid); pool[cur].left = v; } else { if (idx < pool[cur].index) { swap(pool[cur].value, val); swap(pool[cur].index, idx); } auto v = internal_set(pool[cur].right, idx, val, mid, r); pool[cur].right = v; } node_update(cur); return cur; } T internal_get (const int cur, long idx, long l, long r) { if (cur == -1) return e(); if (pool[cur].index == idx) return pool[cur].value; long mid = (l + r) / 2; if (idx < mid) return internal_get(pool[cur].left, idx, l, mid); return internal_get(pool[cur].right, idx, mid, r); } // [a, b) = 要求区間 T internal_prod (const int cur, long a, long b, long l, long r) { if (cur == -1 || b <= l || r <= a) return e(); if (a <= l && r <= b) return pool[cur].product; long mid = (l + r) / 2; T res = internal_prod(pool[cur].left, a, b, l, mid); if (a <= pool[cur].index && pool[cur].index < b) res = op(res, pool[cur].value); res = op(res, internal_prod(pool[cur].right, a, b, mid, r)); return res; } }