Submission #32308
ソースコード
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 | #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 > 0) { 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); } LL query( int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0)r = -1; 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:23:44 |
言語 | C++17 |
状態 | Runtime Error |
得点 | 0 |
ソースコード長 | 1883 Byte |
最大実行時間 | 165 ms |
最大メモリ使用量 | 17328 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 0 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
00_sample_00.in | RE | 160 ms | 480 KB |
1
|
01_small_01.in | WA | 21 ms | 572 KB |
1
|
01_small_02.in | WA | 17 ms | 544 KB |
1
|
01_small_03.in | WA | 21 ms | 384 KB |
1
|
01_small_04.in | WA | 22 ms | 484 KB |
1
|
01_small_05.in | WA | 18 ms | 460 KB |
1
|
01_small_06.in | WA | 19 ms | 440 KB |
1
|
01_small_07.in | WA | 17 ms | 412 KB |
1
|
01_small_08.in | AC | 17 ms | 512 KB |
1
|
01_small_09.in | WA | 15 ms | 488 KB |
1
|
01_small_10.in | WA | 16 ms | 464 KB |
1
|
02_random_01.in | RE | 51 ms | 2744 KB |
1
|
02_random_02.in | WA | 76 ms | 1808 KB |
1
|
02_random_03.in | RE | 103 ms | 5360 KB |
1
|
02_random_04.in | WA | 25 ms | 3396 KB |
1
|
02_random_05.in | RE | 27 ms | 1704 KB |
1
|
02_random_06.in | RE | 102 ms | 4112 KB |
1
|
02_random_07.in | WA | 61 ms | 6504 KB |
1
|
02_random_08.in | RE | 87 ms | 3788 KB |
1
|
02_random_09.in | RE | 25 ms | 2984 KB |
1
|
02_random_10.in | WA | 53 ms | 5132 KB |
1
|
03_large_01.in | RE | 161 ms | 8172 KB |
1
|
03_large_02.in | WA | 156 ms | 9284 KB |
1
|
03_large_03.in | WA | 158 ms | 10148 KB |
1
|
03_large_04.in | WA | 153 ms | 11144 KB |
1
|
03_large_05.in | RE | 165 ms | 12264 KB |
1
|
03_large_06.in | RE | 158 ms | 13252 KB |
1
|
03_large_07.in | RE | 165 ms | 14240 KB |
1
|
03_large_08.in | WA | 155 ms | 15220 KB |
1
|
03_large_09.in | WA | 152 ms | 16336 KB |
1
|
03_large_10.in | RE | 164 ms | 17328 KB |
1
|