Submission #54525

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define inf -2147483647
#define int long long
vector<int> value1;
vector<int> value2;
vector<int> value3;
int N;
void update(int i,int x){
i += N - 1;
value1[i]=x;
value2[i]=x;
value3[i]=x;
while (i > 0) {
i = (i - 1) / 2;
value1[i] = min(value1[i * 2 + 1],value1[i * 2 + 2]);
value2[i] = max(value2[i * 2 + 1],value2[i * 2 + 2]);
value3[i] = value3[i * 2 + 1]+value3[i * 2 + 2];
}
}
void add(int ia,int xa){
ia+=N-1;
value1[ia]=xa+value1[ia];
value2[ia]=xa+value2[ia];
value3[ia]=xa+value3[ia];
while (ia > 0) {
ia = (ia - 1) / 2;
value1[ia] = min(value1[ia * 2 + 1],value1[ia * 2 + 2]);
value2[ia] = max(value2[ia * 2 + 1],value2[ia * 2 + 2]);
value3[ia] = value3[ia * 2 + 1]+value3[ia * 2 + 2];
}
}
int MIN(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) return INF;
if (a <= l && r <= b) return value1[k];
else {
int c1 = MIN(a, b, 2 * k + 1, l, (l + r) / 2);
int c2 = MIN(a, b, 2 * k + 2, (l + r) / 2, r);
return min(c1, c2);
}
}
int MAX(int am,int bm,int km,int lm,int rm){
if(rm<=am||bm<=lm) return inf;
if(am<=lm&&rm<=bm) return value2[km];
else{
int c12=MAX(am,bm,2*km+1,lm,(lm+rm)/2);
int c22=MAX(am,bm,2*km+2,(lm+rm)/2,rm);
return max(c12,c22);
}
}
int SUM(int as,int bs,int ks,int ls,int rs){
if(rs<=as||bs<=ls) return 0;
if(as<=ls&&rs<=bs) return value3[ks];
else{
int c13=SUM(as,bs,2*ks+1,ls,(ls+rs)/2);
int c23=SUM(as,bs,2*ks+2,(ls+rs)/2,rs);
return (c13+c23);
}
}
signed main() {
int n, q;
int s,t;
cin >> n>>q;
N = 1;
while (N < n) N *= 2;
value1 = vector<int>(2 * N - 1, INF);
value2 = vector<int>(2 * N - 1, inf);
value3 = vector<int>(2 * N - 1, 0);
for(int i=0;i<n;i++){
update(i,0);
}
for(int i=0;i<q;i++){
string c;
cin>>c>>s>>t;
if(c=="update") update(s,t);
if(c=="add") add(s,t);
if(c=="getMin") cout<<MIN(s,t,0,0,N)<<"\n";
if(c=="getMax") cout<<MAX(s,t,0,0,N)<<"\n";
if(c=="getSum") cout<<SUM(s,t,0,0,N)<<"\n";
}
return 0;
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 ei1941
投稿日時 2019-09-09 16:16:22
言語 C++11
状態 Accepted
得点 1
ソースコード長 2187 Byte
最大実行時間 208 ms
最大メモリ使用量 12288 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 24 ms 604 KB
1
in02 AC 134 ms 832 KB
1
in03 AC 104 ms 7012 KB
1
in04 AC 138 ms 7228 KB
1
in05 AC 52 ms 7316 KB
1
in06 AC 83 ms 4336 KB
1
in07 AC 105 ms 4420 KB
1
in08 AC 168 ms 3232 KB
1
in09 AC 151 ms 8052 KB
1
in10 AC 185 ms 5320 KB
1
in11 AC 42 ms 3868 KB
1
in12 AC 72 ms 2680 KB
1
in13 AC 149 ms 8732 KB
1
in14 AC 208 ms 4468 KB
1
in15 AC 111 ms 9296 KB
1
in16 AC 147 ms 4140 KB
1
in17 AC 147 ms 9728 KB
1
in18 AC 78 ms 9816 KB
1
in19 AC 154 ms 9908 KB
1
in20 AC 85 ms 10128 KB
1
in21 AC 104 ms 7140 KB
1
in22 AC 174 ms 7484 KB
1
in23 AC 118 ms 10636 KB
1
in24 AC 153 ms 7656 KB
1
in25 AC 158 ms 6340 KB
1
in26 AC 178 ms 11292 KB
1
in27 AC 166 ms 11636 KB
1
in28 AC 200 ms 8908 KB
1
in29 AC 62 ms 11944 KB
1
in30 AC 184 ms 12288 KB
1
in31 AC 100 ms 9308 KB
1
in32 AC 158 ms 9516 KB
1