Submission #62012

ソースコード

?
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
// #include<bits/stdc++.h>
// {{{ Header
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
using namespace std;
// }}}
#define echo cout <<
#define read cin >>
#define fin << '\n'
#define _ << ' ' <<
#define let const auto
#define var auto&&
#define in :
// {{{ SegmentTree
template<class T> struct SegmentTree {
int size;
const T nullValue;
const function<T(T, T)> annex;
vector<T> data;
SegmentTree ( int n, T defaultValue, const function<T(T, T)> f )
: annex(f), nullValue(defaultValue) {
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];
}
};
// }}}
// SegmentTree<int> seg (n, 0, [](int a, int b) { return a+b; } );
/*
#########################################################
# #
# ## ##### # # #### ##### # # ##### #### #
# # # # ## # # # # # # # # # #
# # -- # # # # # # ##### # ##### # # #
# # # # ## # # # # # # # # #
# ##### ##### # # #### ##### # # ##### #### #
# #
#########################################################
*/
// {{{ BinaryIndexedTree
struct BinaryIndexedTree {
vector<int> data;
int size;
BinaryIndexedTree ( int n ) {
this->size = n;
data.resize(n);
}
void add ( int pos, int value ) {
for ( int i = pos; i <= size; i += i & -i ) {
data[i] += value;
}
}
// [1, pos]
int getSum ( int pos ) {
int sum = 0;
for ( int i = pos; i > 0; i -= i & -i ) {
sum += data[i];
}
return sum;
}
const int operator [] ( int pos ) const {
int sum = 0;
for ( int i = pos; i > 0; i -= i & -i ) {
sum += data[i];
}
return sum;
}
int lowerBound ( int value ) {
if ( value <= 0 ) return 0;
int x = 0;
int i = 1;
while ( i*2 <= size ) i *= 2;
for ( ; i > 0; i /= 2 ) {
if ( x + i <= size && data[x+i] < value ) {
value -= data[x+i];
x += i;
}
}
return x+1;
}
};
// }}}
SegmentTree<long long> segmentTree(1000100, 0, [](long long a, long long b){ return a + b; } );
signed main() {
int n, q;
scanf("%d %d", &n, &q);
for ( int i = 0; i < q; i++ ) {
int s, a, b;
scanf("%d %d %d", &s, &a, &b);
if ( s ) {
printf("%lld\n", segmentTree.get(a, b+1));
}
else {
segmentTree.add(a, b);
}
}
return 0;
}

ステータス

項目 データ
問題 0649 - 区間和(セグ木、BIT練習)
ユーザー名 r1825
投稿日時 2020-08-13 09:45:38
言語 C++14
状態 Accepted
得点 5
ソースコード長 4047 Byte
最大実行時間 419 ms
最大メモリ使用量 105100 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 41 ms 17372 KB
1
input100-2 AC 68 ms 18236 KB
1
input100-3 AC 123 ms 20632 KB
1
input100-4 AC 214 ms 25340 KB
1
input100-5 AC 315 ms 32476 KB
1
input1000-1 AC 122 ms 34368 KB
1
input1000-2 AC 263 ms 39456 KB
1
input1000-3 AC 128 ms 41720 KB
1
input1000-4 AC 323 ms 48088 KB
1
input1000-5 AC 116 ms 49852 KB
1
input10000-1 AC 308 ms 55708 KB
1
input10000-2 AC 353 ms 61944 KB
1
input10000-3 AC 288 ms 66780 KB
1
input10000-4 AC 350 ms 72380 KB
1
input10000-5 AC 164 ms 75160 KB
1
input100000-1 AC 387 ms 81656 KB
1
input100000-2 AC 74 ms 82648 KB
1
input100000-3 AC 80 ms 83640 KB
1
input100000-4 AC 212 ms 86932 KB
1
input100000-5 AC 358 ms 92652 KB
1
input1000000-1 AC 66 ms 93124 KB
1
input1000000-2 AC 183 ms 95400 KB
1
input1000000-3 AC 207 ms 97928 KB
1
input1000000-4 AC 419 ms 102760 KB
1
input1000000-5 AC 185 ms 104912 KB
1
input1001000-1 AC 23 ms 105004 KB
1
input1001000-2 AC 23 ms 105100 KB
1
input1001000-3 AC 25 ms 104932 KB
1
input1001000-4 AC 27 ms 104900 KB
1
input1001000-5 AC 20 ms 104864 KB
1