Submission #32311
ソースコード
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 98 99 | #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-19 23:27:01 |
言語 | C++17 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 1937 Byte |
最大実行時間 | 189 ms |
最大メモリ使用量 | 8532 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
00_sample_00.in | AC | 22 ms | 480 KB |
1
|
01_small_01.in | AC | 19 ms | 456 KB |
1
|
01_small_02.in | AC | 18 ms | 556 KB |
1
|
01_small_03.in | AC | 20 ms | 528 KB |
1
|
01_small_04.in | AC | 21 ms | 500 KB |
1
|
01_small_05.in | AC | 22 ms | 600 KB |
1
|
01_small_06.in | AC | 15 ms | 576 KB |
1
|
01_small_07.in | AC | 19 ms | 424 KB |
1
|
01_small_08.in | AC | 15 ms | 404 KB |
1
|
01_small_09.in | AC | 22 ms | 508 KB |
1
|
01_small_10.in | AC | 25 ms | 488 KB |
1
|
02_random_01.in | AC | 49 ms | 2508 KB |
1
|
02_random_02.in | AC | 29 ms | 1580 KB |
1
|
02_random_03.in | AC | 114 ms | 4872 KB |
1
|
02_random_04.in | AC | 25 ms | 2920 KB |
1
|
02_random_05.in | AC | 111 ms | 1224 KB |
1
|
02_random_06.in | AC | 119 ms | 3112 KB |
1
|
02_random_07.in | AC | 68 ms | 5256 KB |
1
|
02_random_08.in | AC | 93 ms | 2280 KB |
1
|
02_random_09.in | AC | 74 ms | 1732 KB |
1
|
02_random_10.in | AC | 60 ms | 3620 KB |
1
|
03_large_01.in | AC | 177 ms | 6016 KB |
1
|
03_large_02.in | AC | 183 ms | 6244 KB |
1
|
03_large_03.in | AC | 189 ms | 6464 KB |
1
|
03_large_04.in | AC | 175 ms | 6812 KB |
1
|
03_large_05.in | AC | 181 ms | 7164 KB |
1
|
03_large_06.in | AC | 181 ms | 7516 KB |
1
|
03_large_07.in | AC | 187 ms | 7864 KB |
1
|
03_large_08.in | AC | 181 ms | 8088 KB |
1
|
03_large_09.in | AC | 185 ms | 8308 KB |
1
|
03_large_10.in | AC | 185 ms | 8532 KB |
1
|