Submission #27605
ソースコード
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 | #include<bits/stdc++.h> using namespace std; template < typename T > struct SegmentTree { const T INF; vector< T > seg, add; int sz; SegmentTree( int n) : INF(-numeric_limits< T >::min() / 5) { sz = 1; while (sz < n) sz <<= 1; seg.assign(2 * sz - 1, 0); add.assign(2 * sz - 1, 0); } T merge(T a, T b) { return (max(a, b)); } void set( int k, int x) { seg[k + sz - 1] = x; } void build() { for ( int k = sz - 2; k >= 0; k--) { seg[k] = merge(seg[2 * k + 1], seg[2 * k + 2]); } } T rmq( int a, int b, int k, int l, int r) { if (a >= r || b <= l) return (INF); if (a <= l && r <= b) return (seg[k] + add[k]); return (merge(rmq(a, b, 2 * k + 1, l, (l + r) >> 1), rmq(a, b, 2 * k + 2, (l + r) >> 1, r)) + add[k]); } T rmq( int a, int b) { return (rmq(a, b, 0, 0, sz)); } void rangeadd( int a, int b, T x, int k, int l, int r) { if (a >= r || b <= l) return ; if (a <= l && r <= b) { add[k] += x; return ; } rangeadd(a, b, x, 2 * k + 1, l, (l + r) >> 1); rangeadd(a, b, x, 2 * k + 2, (l + r) >> 1, r); seg[k] = merge(seg[2 * k + 1] + add[2 * k + 1], seg[2 * k + 2] + add[2 * k + 2]); } void rangeadd( int a, int b, T x) { rangeadd(a, b, x, 0, 0, sz); } }; int main() { int N, Q; scanf ( "%d %d" , &N, &Q); SegmentTree< int > tree(N); for ( int i = 0; i < Q; i++) { int t, a, b; scanf ( "%d %d %d" , &t, &a, &b); if (t == 1) { int x; scanf ( "%d" , &x); tree.rangeadd(a, b, x); } else { printf ( "%d\n" , tree.rmq(a, b)); } } } |
ステータス
項目 | データ |
---|---|
問題 | 0856 - StarrySkyのverify |
ユーザー名 | ei1333 |
投稿日時 | 2017-10-13 23:34:19 |
言語 | C++11 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 1720 Byte |
最大実行時間 | 78 ms |
最大メモリ使用量 | 6544 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
00_sample_00.in | AC | 35 ms | 480 KB |
1
|
01_small_01.in | AC | 19 ms | 456 KB |
1
|
01_small_02.in | AC | 16 ms | 436 KB |
1
|
01_small_03.in | AC | 22 ms | 404 KB |
1
|
01_small_04.in | AC | 14 ms | 380 KB |
1
|
01_small_05.in | AC | 22 ms | 356 KB |
1
|
01_small_06.in | AC | 19 ms | 464 KB |
1
|
01_small_07.in | AC | 17 ms | 564 KB |
1
|
01_small_08.in | AC | 22 ms | 544 KB |
1
|
01_small_09.in | AC | 16 ms | 528 KB |
1
|
01_small_10.in | AC | 22 ms | 504 KB |
1
|
02_random_01.in | AC | 25 ms | 1760 KB |
1
|
02_random_02.in | AC | 18 ms | 1220 KB |
1
|
02_random_03.in | AC | 44 ms | 2852 KB |
1
|
02_random_04.in | AC | 17 ms | 1924 KB |
1
|
02_random_05.in | AC | 49 ms | 1128 KB |
1
|
02_random_06.in | AC | 44 ms | 2132 KB |
1
|
02_random_07.in | AC | 32 ms | 3120 KB |
1
|
02_random_08.in | AC | 40 ms | 1932 KB |
1
|
02_random_09.in | AC | 34 ms | 1644 KB |
1
|
02_random_10.in | AC | 29 ms | 2512 KB |
1
|
03_large_01.in | AC | 72 ms | 3888 KB |
1
|
03_large_02.in | AC | 71 ms | 4108 KB |
1
|
03_large_03.in | AC | 78 ms | 4464 KB |
1
|
03_large_04.in | AC | 67 ms | 4816 KB |
1
|
03_large_05.in | AC | 69 ms | 5044 KB |
1
|
03_large_06.in | AC | 64 ms | 5392 KB |
1
|
03_large_07.in | AC | 65 ms | 5616 KB |
1
|
03_large_08.in | AC | 70 ms | 5964 KB |
1
|
03_large_09.in | AC | 69 ms | 6192 KB |
1
|
03_large_10.in | AC | 65 ms | 6544 KB |
1
|