Submission #32310
ソースコード
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 > 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); } 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:25:34 |
言語 | C++17 |
状態 | Wrong Answer |
得点 | 0 |
ソースコード長 | 1886 Byte |
最大実行時間 | 181 ms |
最大メモリ使用量 | 8664 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 0 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
00_sample_00.in | WA | 24 ms | 476 KB |
1
|
01_small_01.in | AC | 15 ms | 708 KB |
1
|
01_small_02.in | WA | 16 ms | 556 KB |
1
|
01_small_03.in | AC | 21 ms | 656 KB |
1
|
01_small_04.in | AC | 17 ms | 632 KB |
1
|
01_small_05.in | AC | 16 ms | 608 KB |
1
|
01_small_06.in | AC | 17 ms | 584 KB |
1
|
01_small_07.in | AC | 26 ms | 692 KB |
1
|
01_small_08.in | AC | 16 ms | 672 KB |
1
|
01_small_09.in | AC | 25 ms | 648 KB |
1
|
01_small_10.in | AC | 27 ms | 620 KB |
1
|
02_random_01.in | WA | 42 ms | 2772 KB |
1
|
02_random_02.in | WA | 22 ms | 1720 KB |
1
|
02_random_03.in | WA | 104 ms | 5016 KB |
1
|
02_random_04.in | WA | 33 ms | 2940 KB |
1
|
02_random_05.in | WA | 106 ms | 1248 KB |
1
|
02_random_06.in | WA | 114 ms | 3136 KB |
1
|
02_random_07.in | WA | 72 ms | 5276 KB |
1
|
02_random_08.in | WA | 95 ms | 2296 KB |
1
|
02_random_09.in | WA | 84 ms | 1620 KB |
1
|
02_random_10.in | WA | 61 ms | 3512 KB |
1
|
03_large_01.in | WA | 178 ms | 5904 KB |
1
|
03_large_02.in | WA | 181 ms | 6256 KB |
1
|
03_large_03.in | WA | 173 ms | 6600 KB |
1
|
03_large_04.in | WA | 175 ms | 6820 KB |
1
|
03_large_05.in | WA | 174 ms | 7176 KB |
1
|
03_large_06.in | WA | 175 ms | 7392 KB |
1
|
03_large_07.in | WA | 173 ms | 7740 KB |
1
|
03_large_08.in | WA | 175 ms | 8088 KB |
1
|
03_large_09.in | WA | 176 ms | 8440 KB |
1
|
03_large_10.in | WA | 171 ms | 8664 KB |
1
|