Submission #52619

ソースコード

?
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
#include<bits/stdc++.h>
#define FOR(i,n) for(long long i=0;i<n;i++)
#define SFOR(i,a,b) for(long long i=a;i<b;i++)
#define elif(a) else if(a)
#define INF INT_MAX
#define F first
#define S second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
class segment{
public:
vector<ll>value;
int N;
segment(int n){
N=n;
value.resize(N*2-1,0);
}
void update(int i,ll x){
i+=N-1;
value[i]+=x;
while(i>0){
i=(i-1)/2;
value[i]=value[i*2+1]+value[i*2+2];
}
return;
}
ll find(int a,int b,int k,int l,int r){
if(r<=a || b<=l) return 0;
if(a<=l && r<=b) return value[k];
else{
ll m1=find(a,b,k*2+1,l,(l+r)/2);
ll m2=find(a,b,k*2+2,(l+r)/2,r);
return m1+m2;
}
}
};
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n,q;
cin>>n>>q;
int N=1;
while(N<n) N*=2;
segment tree(N);
ll s,a,b;
FOR(i,q){
cin>>s>>a>>b;
if(s==0) tree.update(a-1,b);
else cout<<tree.find(a-1,b,0,0,N)<<endl;
}
return 0;
}

ステータス

項目 データ
問題 0649 - 区間和(セグ木、BIT練習)
ユーザー名 Zzz..ei1704..Zzz
投稿日時 2019-08-09 11:09:55
言語 C++14
状態 Accepted
得点 5
ソースコード長 1110 Byte
最大実行時間 333 ms
最大メモリ使用量 104940 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 40 ms 988 KB
1
input100-2 AC 53 ms 1956 KB
1
input100-3 AC 85 ms 4204 KB
1
input100-4 AC 158 ms 8760 KB
1
input100-5 AC 222 ms 15996 KB
1
input1000-1 AC 93 ms 17984 KB
1
input1000-2 AC 190 ms 23168 KB
1
input1000-3 AC 96 ms 25528 KB
1
input1000-4 AC 229 ms 31732 KB
1
input1000-5 AC 83 ms 33588 KB
1
input10000-1 AC 240 ms 39536 KB
1
input10000-2 AC 265 ms 45880 KB
1
input10000-3 AC 214 ms 50820 KB
1
input10000-4 AC 230 ms 56524 KB
1
input10000-5 AC 135 ms 59156 KB
1
input100000-1 AC 322 ms 67424 KB
1
input100000-2 AC 70 ms 68264 KB
1
input100000-3 AC 67 ms 69360 KB
1
input100000-4 AC 208 ms 72508 KB
1
input100000-5 AC 261 ms 78344 KB
1
input1000000-1 AC 62 ms 93260 KB
1
input1000000-2 AC 171 ms 95512 KB
1
input1000000-3 AC 172 ms 98020 KB
1
input1000000-4 AC 333 ms 102952 KB
1
input1000000-5 AC 154 ms 104940 KB
1
input1001000-1 AC 24 ms 88632 KB
1
input1001000-2 AC 19 ms 88580 KB
1
input1001000-3 AC 20 ms 88652 KB
1
input1001000-4 AC 19 ms 88724 KB
1
input1001000-5 AC 19 ms 88544 KB
1