Submission #52742

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
template<class T>
struct SegmentTree {
int size;
const T nullValue;
const function<T(T, T)> annex;
vector<T> data;
SegmentTree ( int n, T defaultValue, T nullValue, const function<T(T, T)> f )
: annex(f), nullValue(nullValue) {
for ( size = 1; size < n; size *= 2 );
data.resize ( 2*size-1, defaultValue );
}
void update ( int pos, T value ) {
pos += size-1;
data[pos] = value;
while ( pos > 0 ) {
pos = ( pos - 1 ) / 2;
data[pos] = annex ( data[pos*2+1], data[pos*2+2] );
}
}
T add ( int pos, T value ) {
update ( pos, value + data[pos+size-1] );
return data[pos+size-1];
}
T get ( int begin, int end, int pos=0, int left=0, int right=-1 ) {
if ( right == -1 ) right = size;
if ( right <= begin || end <= left ) return nullValue;
if ( begin <= left && right <= end ) return data[pos];
int next = ( left + right ) / 2;
return annex ( get ( begin, end, pos*2+1, left, next ), get ( begin, end, pos*2+2, next, right ) );
}
inline const T& operator [] ( int index ) const {
return data[index+size-1];
}
inline T& operator [] ( int index ) {
return data[index+size-1];
}
};
signed main ( ) {
int n, m;
scanf("%d %d", &n, &m);
SegmentTree<int> mi ( n, 0, 0x3f3f3f3f , [](int a, int b){return min(a, b);} );
SegmentTree<int> ma ( n, 0, -0x3f3f3f3f, [](int a, int b){return max(a, b);} );
SegmentTree<int> su ( n, 0, 0, [](int a, int b){return a+b;} );
for ( int i = 0; i < m; i++ ) {
string s;
int a, b;
cin >> s;
scanf("%d %d", &a, &b);
if ( s == "add" ) {
mi.add(a, b);
ma.add(a, b);
su.add(a, b);
}
else if ( s == "update" ) {
mi.update(a, b);
ma.update(a, b);
su.update(a, b);
}
else if ( s == "getMin" ) {
printf("%d\n", mi.get(a, b));
}
else if ( s == "getMax" ) {
printf("%d\n", ma.get(a, b));
}
else if ( s == "getSum" ){
printf("%d\n", su.get(a, b));
}
}
return 0;
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 r1825
投稿日時 2019-08-14 09:53:04
言語 C++14
状態 Accepted
得点 1
ソースコード長 2384 Byte
最大実行時間 191 ms
最大メモリ使用量 9160 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 28 ms 604 KB
1
in02 AC 132 ms 960 KB
1
in03 AC 96 ms 4036 KB
1
in04 AC 143 ms 4256 KB
1
in05 AC 43 ms 4220 KB
1
in06 AC 72 ms 2768 KB
1
in07 AC 94 ms 2988 KB
1
in08 AC 168 ms 2440 KB
1
in09 AC 134 ms 4832 KB
1
in10 AC 159 ms 3636 KB
1
in11 AC 46 ms 2960 KB
1
in12 AC 69 ms 2408 KB
1
in13 AC 139 ms 5608 KB
1
in14 AC 191 ms 3652 KB
1
in15 AC 107 ms 6172 KB
1
in16 AC 141 ms 3696 KB
1
in17 AC 133 ms 6600 KB
1
in18 AC 64 ms 6688 KB
1
in19 AC 127 ms 6900 KB
1
in20 AC 79 ms 6992 KB
1
in21 AC 92 ms 5672 KB
1
in22 AC 171 ms 5888 KB
1
in23 AC 109 ms 7516 KB
1
in24 AC 128 ms 6196 KB
1
in25 AC 139 ms 5644 KB
1
in26 AC 161 ms 8296 KB
1
in27 AC 158 ms 8640 KB
1
in28 AC 179 ms 7324 KB
1
in29 AC 66 ms 8820 KB
1
in30 AC 140 ms 9160 KB
1
in31 AC 95 ms 7844 KB
1
in32 AC 140 ms 8056 KB
1