Submission #62013

ソースコード

?
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
161
// #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; } );
#define int long long
/*
#########################################################
# #
# ## ##### # # #### ##### # # ##### #### #
# # # # ## # # # # # # # # # #
# # -- # # # # # # ##### # ##### # # #
# # # # ## # # # # # # # # #
# ##### ##### # # #### ##### # # ##### #### #
# #
#########################################################
*/
// {{{ 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;
}
};
// }}}
BinaryIndexedTree bit(1000100);
signed main() {
int n, q;
scanf("%lld %lld", &n, &q);
for ( int i = 0; i < q; i++ ) {
int s, a, b;
scanf("%lld %lld %lld", &s, &a, &b);
if ( s ) {
printf("%lld\n", bit.getSum(b) - bit.getSum(a-1));
}
else {
bit.add(a, b);
}
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 41 ms 8796 KB
1
input100-2 AC 55 ms 9660 KB
1
input100-3 AC 87 ms 11924 KB
1
input100-4 AC 153 ms 16628 KB
1
input100-5 AC 225 ms 23892 KB
1
input1000-1 AC 94 ms 25904 KB
1
input1000-2 AC 169 ms 30984 KB
1
input1000-3 AC 87 ms 33252 KB
1
input1000-4 AC 219 ms 39616 KB
1
input1000-5 AC 75 ms 41500 KB
1
input10000-1 AC 192 ms 47100 KB
1
input10000-2 AC 211 ms 53464 KB
1
input10000-3 AC 169 ms 58424 KB
1
input10000-4 AC 186 ms 64024 KB
1
input10000-5 AC 106 ms 66804 KB
1
input100000-1 AC 225 ms 73172 KB
1
input100000-2 AC 58 ms 74032 KB
1
input100000-3 AC 52 ms 75144 KB
1
input100000-4 AC 131 ms 78308 KB
1
input100000-5 AC 206 ms 84032 KB
1
input1000000-1 AC 45 ms 84640 KB
1
input1000000-2 AC 100 ms 86780 KB
1
input1000000-3 AC 124 ms 89432 KB
1
input1000000-4 AC 199 ms 94388 KB
1
input1000000-5 AC 112 ms 96400 KB
1
input1001000-1 AC 22 ms 96368 KB
1
input1001000-2 AC 23 ms 96460 KB
1
input1001000-3 AC 19 ms 96424 KB
1
input1001000-4 AC 30 ms 96392 KB
1
input1001000-5 AC 19 ms 96348 KB
1