結果
問題 | No.876 Range Compress Query |
ユーザー | startcpp |
提出日時 | 2019-09-06 21:39:32 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 228 ms / 2,000 ms |
コード長 | 1,184 bytes |
コンパイル時間 | 671 ms |
コンパイル使用メモリ | 53,480 KB |
実行使用メモリ | 8,252 KB |
最終ジャッジ日時 | 2023-09-06 23:09:29 |
合計ジャッジ時間 | 3,809 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
7,440 KB |
testcase_01 | AC | 4 ms
7,440 KB |
testcase_02 | AC | 4 ms
7,504 KB |
testcase_03 | AC | 4 ms
7,444 KB |
testcase_04 | AC | 4 ms
7,456 KB |
testcase_05 | AC | 4 ms
7,680 KB |
testcase_06 | AC | 5 ms
7,436 KB |
testcase_07 | AC | 4 ms
7,456 KB |
testcase_08 | AC | 5 ms
7,456 KB |
testcase_09 | AC | 5 ms
7,500 KB |
testcase_10 | AC | 4 ms
7,456 KB |
testcase_11 | AC | 222 ms
8,184 KB |
testcase_12 | AC | 184 ms
7,968 KB |
testcase_13 | AC | 185 ms
8,040 KB |
testcase_14 | AC | 219 ms
8,156 KB |
testcase_15 | AC | 158 ms
8,100 KB |
testcase_16 | AC | 215 ms
8,252 KB |
testcase_17 | AC | 212 ms
8,220 KB |
testcase_18 | AC | 228 ms
8,244 KB |
ソースコード
//階差 #include <iostream> #define int long long #define rep(i, n) for(i = 0; i < (n); i++) using namespace std; const int DEPTH = 17; struct SegTree { int d[1 << (DEPTH + 1)]; int f[1 << (DEPTH + 1)]; SegTree() { int i; rep(i, 1 << (DEPTH + 1)) { d[i] = 0; f[i] = 0; } } void add(int pos, int x) { pos += (1 << DEPTH) - 1; d[pos] += x; f[pos] = (d[pos] != 0); while (pos > 0) { pos = (pos - 1) / 2; d[pos] = d[pos * 2 + 1] + d[pos * 2 + 2]; f[pos] = f[pos * 2 + 1] + f[pos * 2 + 2]; } } int fsum(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) { if (a >= r || b <= l) return 0; if (l <= a && b <= r) return f[id]; int x = fsum(l, r, a, (a + b) / 2, id * 2 + 1); int y = fsum(l, r, (a + b) / 2, b, id * 2 + 2); return x + y; } }; int n, q; int a[100000]; int t, l, r; SegTree seg; signed main() { int i; cin >> n >> q; rep(i, n) cin >> a[i]; rep(i, n - 1) seg.add(i + 1, a[i + 1] - a[i]); //セグ木は、1-indexed rep(i, q) { cin >> t >> l >> r; l--; r--; if (t == 1) { int x; cin >> x; seg.add(l, x); seg.add(r + 1, -x); } else { cout << seg.fsum(l + 1, r + 1) + 1 << endl; } } return 0; }