Submission #58556

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
#define pb push_back
#define INF 1e15
class SegTree {
public:
int n;
VL nodes;
VL lazy;
SegTree(VL a) {
int size = a.size();
n = 1;
while(n < size) n *= 2;
nodes.resize(n * 2 - 1, 0);
lazy.resize(n * 2 - 1, 0);
for (int i = 0; i < size; ++i) {
nodes[n - 1 + i] = a[i];
}
for (int i = n - 2; i >= 0; --i) {
nodes[i] = nodes[i * 2 + 1] + nodes[i * 2 + 2];
}
}
void add(int a, ll x) {
a += n - 1;
nodes[a] += x;
while(a > 0) {
a = (a - 1) / 2;
nodes[a] = nodes[a * 2 + 1] + nodes[a * 2 + 2];
}
}
ll get(int a, int b, int k = 0, int l = 0, int r = -1) {
if(r < 0) r = n;
if(r <= a || l >= b) return 0;
if(a <= l && r <= b) return nodes[k];
return get(a, b, k * 2 + 1, l, (l + r) / 2)
+ get(a, b, k * 2 + 2, (l + r) / 2, r);
}
};
int main(int argc, char **argv) {
int n, q;
cin >> n >> q;
VL a(n, 0);
SegTree st(a);
VVL qu(q, VL(3));
for (int i = 0; i < q; ++i) {
cin >> qu[i][0] >> qu[i][1] >> qu[i][2];
}
for (int i = 0; i < q; ++i) {
if(qu[i][0] == 0) {
st.add(qu[i][1] - 1, qu[i][2]);
}else {
cout << st.get(qu[i][1] - 1, qu[i][2]) << endl;
}
}
return 0;
}

ステータス

項目 データ
問題 0649 - 区間和(セグ木、BIT練習)
ユーザー名 shun0923
投稿日時 2020-02-08 22:24:27
言語 C++14
状態 Accepted
得点 5
ソースコード長 1475 Byte
最大実行時間 1419 ms
最大メモリ使用量 164684 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 110 ms 3928 KB
1
input100-2 AC 228 ms 10016 KB
1
input100-3 AC 471 ms 22096 KB
1
input100-4 AC 933 ms 44832 KB
1
input100-5 AC 1379 ms 70092 KB
1
input1000-1 AC 480 ms 34400 KB
1
input1000-2 AC 1039 ms 61848 KB
1
input1000-3 AC 467 ms 42884 KB
1
input1000-4 AC 1282 ms 80032 KB
1
input1000-5 AC 395 ms 47784 KB
1
input10000-1 AC 1224 ms 83556 KB
1
input10000-2 AC 1323 ms 94152 KB
1
input10000-3 AC 1046 ms 88824 KB
1
input10000-4 AC 1213 ms 99736 KB
1
input10000-5 AC 617 ms 81308 KB
1
input100000-1 AC 1419 ms 119368 KB
1
input100000-2 AC 242 ms 78724 KB
1
input100000-3 AC 256 ms 80164 KB
1
input100000-4 AC 750 ms 101112 KB
1
input100000-5 AC 1262 ms 124924 KB
1
input1000000-1 AC 173 ms 124788 KB
1
input1000000-2 AC 562 ms 136648 KB
1
input1000000-3 AC 641 ms 141812 KB
1
input1000000-4 AC 1204 ms 164684 KB
1
input1000000-5 AC 551 ms 145676 KB
1
input1001000-1 AC 21 ms 88588 KB
1
input1001000-2 AC 20 ms 88632 KB
1
input1001000-3 AC 21 ms 88576 KB
1
input1001000-4 AC 20 ms 88616 KB
1
input1001000-5 AC 23 ms 88704 KB
1