Submission #81784

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
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;
}
};
int main(){
#define int long
int n,q;cin>>n>>q;
//Tree<戻り値の型> [](マージ型){マージ},戻り値
SegmentTree< int > seg(n, [](int a, int b) {
return a+b;
},
0);
for(int i=0;i<q;i++){
int s,a,b;cin>>s>>a>>b;
if(s==0){
seg.update(a-1,seg[a-1]+b);
}else{
cout<<seg.query(a-1,b)<<"\n";
}
}
/* int n,a;cin>>n>>a;
string s="X";cin>>s;
s+="X";
for(int i=0;i<s.size();i++){
} */
}

ステータス

項目 データ
問題 0649 - 区間和(セグ木、BIT練習)
ユーザー名 ei2331
投稿日時 2024-12-05 15:24:18
言語 C++17
状態 Accepted
得点 5
ソースコード長 2530 Byte
最大実行時間 1453 ms
最大メモリ使用量 104972 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 106 ms 988 KB
1
input100-2 AC 238 ms 1984 KB
1
input100-3 AC 495 ms 4124 KB
1
input100-4 AC 960 ms 8824 KB
1
input100-5 AC 1431 ms 15956 KB
1
input1000-1 AC 447 ms 18100 KB
1
input1000-2 AC 1050 ms 23176 KB
1
input1000-3 AC 487 ms 25312 KB
1
input1000-4 AC 1287 ms 31672 KB
1
input1000-5 AC 402 ms 33676 KB
1
input10000-1 AC 1239 ms 39516 KB
1
input10000-2 AC 1402 ms 45880 KB
1
input10000-3 AC 1057 ms 50708 KB
1
input10000-4 AC 1208 ms 56312 KB
1
input10000-5 AC 615 ms 59096 KB
1
input100000-1 AC 1453 ms 67384 KB
1
input100000-2 AC 251 ms 68372 KB
1
input100000-3 AC 251 ms 69364 KB
1
input100000-4 AC 772 ms 72660 KB
1
input100000-5 AC 1268 ms 78392 KB
1
input1000000-1 AC 162 ms 93204 KB
1
input1000000-2 AC 548 ms 95344 KB
1
input1000000-3 AC 619 ms 97872 KB
1
input1000000-4 AC 1185 ms 102828 KB
1
input1000000-5 AC 535 ms 104972 KB
1
input1001000-1 AC 24 ms 88556 KB
1
input1001000-2 AC 17 ms 88524 KB
1
input1001000-3 AC 33 ms 88620 KB
1
input1001000-4 AC 21 ms 88588 KB
1
input1001000-5 AC 20 ms 88688 KB
1