Submission #42480

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> P;
const int SIZE = 1000005;
int n;
long long bit[1000005]={};
void add(int i, long long x);
long long sum(int i);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
cin >> n >> q;
for(int i=0;i<q;i++){
int a,b;
cin >> a >> b;
if(a == 0){
long long c;
cin >> c;
add(b, c);
} else{
int c;
cin >> c;
cout << sum(c)-sum(b-1) << endl;
}
}
return 0;
}
void add(int i, long long x)
{
while(i < SIZE){
bit[i] += x;
i += i&(-i);
}
return;
}
long long sum(int i)
{
if(i == 0) return 0;
long long s=0;
while(i > 0){
s += bit[i];
i -= i&(-i);
}
return s;
}

ステータス

項目 データ
問題 0649 - 区間和(セグ木、BIT練習)
ユーザー名 ei1612
投稿日時 2018-08-31 12:02:22
言語 C++11
状態 Accepted
得点 5
ソースコード長 813 Byte
最大実行時間 1073 ms
最大メモリ使用量 104412 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 96 ms 5472 KB
1
input100-2 AC 232 ms 8328 KB
1
input100-3 AC 412 ms 14264 KB
1
input100-4 AC 738 ms 20960 KB
1
input100-5 AC 1073 ms 28172 KB
1
input1000-1 AC 335 ms 30260 KB
1
input1000-2 AC 778 ms 35300 KB
1
input1000-3 AC 354 ms 37524 KB
1
input1000-4 AC 949 ms 43840 KB
1
input1000-5 AC 308 ms 45672 KB
1
input10000-1 AC 890 ms 51476 KB
1
input10000-2 AC 965 ms 57856 KB
1
input10000-3 AC 763 ms 62700 KB
1
input10000-4 AC 896 ms 68308 KB
1
input10000-5 AC 438 ms 71104 KB
1
input100000-1 AC 1012 ms 78252 KB
1
input100000-2 AC 172 ms 79068 KB
1
input100000-3 AC 173 ms 80016 KB
1
input100000-4 AC 531 ms 83392 KB
1
input100000-5 AC 870 ms 89072 KB
1
input1000000-1 AC 126 ms 92444 KB
1
input1000000-2 AC 377 ms 94696 KB
1
input1000000-3 AC 445 ms 97208 KB
1
input1000000-4 AC 831 ms 102280 KB
1
input1000000-5 AC 371 ms 104412 KB
1
input1001000-1 AC 21 ms 100648 KB
1
input1001000-2 AC 26 ms 100568 KB
1
input1001000-3 AC 25 ms 100736 KB
1
input1001000-4 AC 24 ms 100780 KB
1
input1001000-5 AC 30 ms 100704 KB
1