Submission #32341
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <cstring> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <list> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <unordered_set> #include <unordered_map> #include <array> #include <cassert> #include <bitset> using namespace std; using LL = long long ; struct StarrySky { vector<LL>seg, laz; int width; StarrySky( int n) :width(1) { while (width < n)width *= 2; seg.resize(width * 2 - 1); laz.resize(width * 2 - 1); } void eval( int k, int l, int r) { if (laz[k] == 0) return ; if (r - l > 1) { laz[k * 2 + 1] += laz[k]; laz[k * 2 + 2] += laz[k]; } seg[k] += laz[k]; laz[k] = 0; } void add( int a, int b, LL val, int k = 0, int l = 0, int r = -1) { if (r < 0) r = width; eval(k, l, r); if (r <= a || b <= l) { return ; } if (a <= l&&r <= b) { laz[k] += val; eval(k, l, r); return ; } add(a, b, val, k * 2 + 1, l, (l + r) / 2); add(a, b, val, k * 2 + 2, (l + r) / 2, r); seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]); } LL query( int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = width; eval(k, l, r); if (r <= a || b <= l) { return LLONG_MIN; } if (a <= l&&r <= b) { return seg[k]; } return max( query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r)); } }; int N, Q; int main() { cin >> N >> Q; StarrySky sky(N); for ( int i = 0; i < Q; ++i) { int t; cin >> t; if (t == 1) { LL a, b, x; cin >> a >> b >> x; sky.add(a, b, x); } else { LL a, b; cin >> a >> b; LL ans = sky.query(a, b); cout << ans << endl; } } } |
ステータス
項目 | データ |
---|---|
問題 | 0856 - StarrySkyのverify |
ユーザー名 | platypus |
投稿日時 | 2018-03-20 23:19:08 |
言語 | C++17 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 1923 Byte |
最大実行時間 | 192 ms |
最大メモリ使用量 | 8580 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
00_sample_00.in | AC | 23 ms | 480 KB |
1
|
01_small_01.in | AC | 24 ms | 712 KB |
1
|
01_small_02.in | AC | 15 ms | 556 KB |
1
|
01_small_03.in | AC | 15 ms | 404 KB |
1
|
01_small_04.in | AC | 18 ms | 384 KB |
1
|
01_small_05.in | AC | 20 ms | 492 KB |
1
|
01_small_06.in | AC | 16 ms | 600 KB |
1
|
01_small_07.in | AC | 16 ms | 576 KB |
1
|
01_small_08.in | AC | 25 ms | 552 KB |
1
|
01_small_09.in | AC | 18 ms | 528 KB |
1
|
01_small_10.in | AC | 14 ms | 500 KB |
1
|
02_random_01.in | AC | 48 ms | 2652 KB |
1
|
02_random_02.in | AC | 32 ms | 1596 KB |
1
|
02_random_03.in | AC | 120 ms | 4892 KB |
1
|
02_random_04.in | AC | 26 ms | 2816 KB |
1
|
02_random_05.in | AC | 113 ms | 1248 KB |
1
|
02_random_06.in | AC | 116 ms | 3140 KB |
1
|
02_random_07.in | AC | 69 ms | 5280 KB |
1
|
02_random_08.in | AC | 96 ms | 2308 KB |
1
|
02_random_09.in | AC | 79 ms | 1760 KB |
1
|
02_random_10.in | AC | 65 ms | 3652 KB |
1
|
03_large_01.in | AC | 192 ms | 5920 KB |
1
|
03_large_02.in | AC | 187 ms | 6144 KB |
1
|
03_large_03.in | AC | 187 ms | 6492 KB |
1
|
03_large_04.in | AC | 180 ms | 6844 KB |
1
|
03_large_05.in | AC | 180 ms | 7200 KB |
1
|
03_large_06.in | AC | 178 ms | 7424 KB |
1
|
03_large_07.in | AC | 186 ms | 7648 KB |
1
|
03_large_08.in | AC | 180 ms | 8000 KB |
1
|
03_large_09.in | AC | 183 ms | 8224 KB |
1
|
03_large_10.in | AC | 184 ms | 8580 KB |
1
|