Submission #62096

ソースコード

?
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
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <bits/stdc++.h>
//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i > (n); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define Unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fi > xed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T> //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T> //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) { //多次元初期化
std::fill((T *)array, (T *)(array + N), val);
}
template <class A, class B>
bool chmax(A &a, const B &b) { //最大値更新 返り値はbool
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class A, class B>
bool chmin(A &a, const B &b) { //最小値更新 返り値はbool
if (b < a) {
a = b;
return 1;
}
return 0;
}
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END
template <typename Monoid>
struct SegmentTree {
using F = function<Monoid(Monoid, Monoid)>;
int sz;
vector<Monoid> seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
sz = 1;
while (sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) { seg[k + sz] = x; }
void build() {
for (int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while (k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if (a & 1) L = f(L, seg[a++]);
if (b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const { return seg[k + sz]; }
template <typename C>
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while (a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if (check(nxt))
a = 2 * a + type;
else
M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template <typename C>
int find_first(int a, const C &check) {
Monoid L = M1;
if (a <= 0) {
if (check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return -1;
}
int b = sz;
for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if (a & 1) {
Monoid nxt = f(L, seg[a]);
if (check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template <typename C>
int find_last(int b, const C &check) {
Monoid R = M1;
if (b >= sz) {
if (check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for (b += sz; a < b; a >>= 1, b >>= 1) {
if (b & 1) {
Monoid nxt = f(seg[--b], R);
if (check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
signed main(void) {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
SegmentTree<int> seg(
n, [](int a, int b) { return (a + b); }, 0);
rep(i, 0, q) {
int com, a, b;
cin >> com >> a >> b;
--a;
if (com == 0) {
int now = seg[a];
seg.update(a, now + b);
} else {
cout << seg.query(a, b) << '\n';
}
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 36 ms 988 KB
1
input100-2 AC 53 ms 2084 KB
1
input100-3 AC 85 ms 4332 KB
1
input100-4 AC 155 ms 8884 KB
1
input100-5 AC 216 ms 16000 KB
1
input1000-1 AC 87 ms 18124 KB
1
input1000-2 AC 184 ms 23172 KB
1
input1000-3 AC 93 ms 25540 KB
1
input1000-4 AC 225 ms 31872 KB
1
input1000-5 AC 83 ms 33728 KB
1
input10000-1 AC 220 ms 39676 KB
1
input10000-2 AC 238 ms 45888 KB
1
input10000-3 AC 198 ms 50700 KB
1
input10000-4 AC 221 ms 56280 KB
1
input10000-5 AC 115 ms 59168 KB
1
input100000-1 AC 275 ms 67432 KB
1
input100000-2 AC 57 ms 68276 KB
1
input100000-3 AC 62 ms 69248 KB
1
input100000-4 AC 148 ms 72524 KB
1
input100000-5 AC 241 ms 78232 KB
1
input1000000-1 AC 55 ms 93152 KB
1
input1000000-2 AC 132 ms 95392 KB
1
input1000000-3 AC 151 ms 97892 KB
1
input1000000-4 AC 275 ms 102960 KB
1
input1000000-5 AC 121 ms 104952 KB
1
input1001000-1 AC 24 ms 88512 KB
1
input1001000-2 AC 18 ms 88576 KB
1
input1001000-3 AC 25 ms 88648 KB
1
input1001000-4 AC 18 ms 88720 KB
1
input1001000-5 AC 16 ms 88668 KB
1