Submission #47761

ソースコード

?
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;
static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
int dx[] = {0, -1, 1, 0};
int dy[] = {-1, 0, 0, 1};
void init( int size );
void update( int pos, int dat, int size );
void add( int pos, int dat, int size );
int getMin( int a, int b, int pos, int left, int right );
int getMax( int a, int b, int pos, int left, int right );
int getSum( int a, int b, int pos, int left, int right );
typedef struct {
int min_v;
int max_v;
int sum_v;
} Data;
Data segtree[1000005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
int bin = 1;
while( bin < n ) bin *= 2;
n = bin;
init( n );
for( int i = 0; i < m; ++i ) {
string s;
int p, q;
cin >> s >> p >> q;
if( s == "update" ) update( p, q, n );
if( s == "add" ) add( p, q, n );
if( s == "getMin" ) cout << getMin( p, q, 0, 0, n ) << endl;
if( s == "getMax" ) cout << getMax( p, q, 0, 0, n ) << endl;
if( s == "getSum" ) cout << getSum( p, q, 0, 0, n ) << endl;
}
return 0;
}
void init( int size )
{
for( int i = 0; i < size * 2 + 1; ++i ) {
segtree[i].min_v = 0;
segtree[i].max_v = 0;
segtree[i].sum_v = 0;
}
return;
}
void update( int pos, int dat, int size )
{
pos += size - 1;
segtree[pos].min_v = dat;
segtree[pos].max_v = dat;
segtree[pos].sum_v = dat;
while( pos > 0 ) {
pos = ( pos - 1 ) / 2;
segtree[pos].min_v = min( segtree[pos * 2 + 1].min_v, segtree[pos * 2 + 2].min_v );
segtree[pos].max_v = max( segtree[pos * 2 + 1].max_v, segtree[pos * 2 + 2].max_v );
segtree[pos].sum_v = segtree[pos * 2 + 1].sum_v + segtree[pos * 2 + 2].sum_v;
}
return;
}
void add( int pos, int dat, int size )
{
pos += size - 1;
segtree[pos].min_v += dat;
segtree[pos].max_v += dat;
segtree[pos].sum_v += dat;
while( pos > 0 ) {
pos = ( pos - 1 ) / 2;
segtree[pos].min_v = min( segtree[pos * 2 + 1].min_v, segtree[pos * 2 + 2].min_v );
segtree[pos].max_v = max( segtree[pos * 2 + 1].max_v, segtree[pos * 2 + 2].max_v );
segtree[pos].sum_v = segtree[pos * 2 + 1].sum_v + segtree[pos * 2 + 2].sum_v;
}
return;
}
int getMin( int a, int b, int pos, int left, int right )
{
if( right <= a || b <= left ) return INF;
if( a <= left && right <= b ) return segtree[pos].min_v;
return min(
getMin( a, b, pos * 2 + 1, left, ( left + right ) / 2 ),
getMin( a, b, pos * 2 + 2, ( left + right ) / 2, right )
);
}
int getMax( int a, int b, int pos, int left, int right )
{
if( right <= a || b <= left ) return -INF;
if( a <= left && right <= b ) return segtree[pos].max_v;
return max(
getMax( a, b, pos * 2 + 1, left, ( left + right ) / 2 ),
getMax( a, b, pos * 2 + 2, ( left + right ) / 2, right )
);
}
int getSum( int a, int b, int pos, int left, int right )
{
if( right <= a || b <= left ) return 0;
if( a <= left && right <= b ) return segtree[pos].sum_v;
return (
getSum( a, b, pos * 2 + 1, left, ( left + right ) / 2 ) +
getSum( a, b, pos * 2 + 2, ( left + right ) / 2, right )
);
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 crom
投稿日時 2019-03-17 22:55:36
言語 C++11
状態 Accepted
得点 1
ソースコード長 3820 Byte
最大実行時間 141 ms
最大メモリ使用量 10272 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 141 ms 604 KB
1
in02 AC 51 ms 944 KB
1
in03 AC 43 ms 4892 KB
1
in04 AC 52 ms 5108 KB
1
in05 AC 33 ms 5192 KB
1
in06 AC 38 ms 2712 KB
1
in07 AC 46 ms 2788 KB
1
in08 AC 55 ms 2484 KB
1
in09 AC 50 ms 6012 KB
1
in10 AC 56 ms 3668 KB
1
in11 AC 34 ms 3108 KB
1
in12 AC 39 ms 2416 KB
1
in13 AC 50 ms 6616 KB
1
in14 AC 67 ms 3624 KB
1
in15 AC 42 ms 7156 KB
1
in16 AC 48 ms 3660 KB
1
in17 AC 50 ms 7704 KB
1
in18 AC 34 ms 7784 KB
1
in19 AC 51 ms 7996 KB
1
in20 AC 44 ms 7948 KB
1
in21 AC 48 ms 5604 KB
1
in22 AC 61 ms 5932 KB
1
in23 AC 54 ms 8692 KB
1
in24 AC 52 ms 6340 KB
1
in25 AC 50 ms 5776 KB
1
in26 AC 58 ms 9308 KB
1
in27 AC 51 ms 9524 KB
1
in28 AC 58 ms 7432 KB
1
in29 AC 29 ms 10060 KB
1
in30 AC 52 ms 10272 KB
1
in31 AC 36 ms 7920 KB
1
in32 AC 52 ms 8124 KB
1