Submission #69132

ソースコード

?
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
#include<bits/stdc++.h> //1072 - セグメントツリー技術基礎
#define dou double //参考 - ei2009
#define ll long long
#define int2 int,int
#define all(x) x.begin(),x.end()
#define gi greater<int>()
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fir first
#define sec second
#define uns unsigned
using namespace std;
struct seg{
int n,inf=30000,m_inf=-30000;
vector<ll> v_sum; //値の合計
vector<ll> v_min; //最小値
vector<ll> v_max; //最大値
//配列初期化
seg(int size){
n=1;
while(n<size){
n*=2;
}
v_sum.resize(n*2);
v_min.resize(n*2);
v_max.resize(n*2);
for(int i=0;i<n*2;i++){
v_sum[i]=0;
v_min[i]=0;
v_max[i]=0;
}
}
//値の更新
void update(int i,int x){
i+=n-1;
v_sum[i]=x;
v_min[i]=x;
v_max[i]=x;
while(i>0){
i=(i-1)/2;
v_sum[i]=v_sum[i*2+1]+v_sum[i*2+2];
v_min[i]=min(v_min[i*2+1],v_min[i*2+2]);
v_max[i]=max(v_max[i*2+1],v_max[i*2+2]);
}
}
//値の加算
void add(int i,int x){
i+=n-1;
v_sum[i]+=x;
v_min[i]+=x;
v_max[i]+=x;
while(i>0){
i=(i-1)/2;
v_sum[i]=v_sum[i*2+1]+v_sum[i*2+2];
v_min[i]=min(v_min[i*2+1],v_min[i*2+2]);
v_max[i]=max(v_max[i*2+1],v_max[i*2+2]);
}
}
//最小値の取得
int getMin(int a,int b){
return getlit(a,b,0,0,n);
}
int getlit(int a,int b,int i,int l,int r){
if(r<=a||b<=l){ //完全に範囲外
return inf;
}else if(a<=l&&r<=b){ //完全に範囲内
return v_min[i];
}else{ //一部区間が被る
int min_l=getlit(a,b,i*2+1,l,(l+r)/2);
int min_r=getlit(a,b,i*2+2,(l+r)/2,r);
return min(min_l,min_r);
}
}
//最大値の取得
int getMax(int a,int b){
return getbig(a,b,0,0,n);
}
int getbig(int a,int b,int i,int l,int r){
if(r<=a||b<=l){
return m_inf;
}else if(a<=l&&r<=b){
return v_max[i];
}else{
int max_l=getbig(a,b,i*2+1,l,(l+r)/2);
int max_r=getbig(a,b,i*2+2,(l+r)/2,r);
return max(max_l,max_r);
}
}
//合計値の取得
int getSum(int a,int b){
return gettot(a,b,0,0,n);
}
int gettot(int a,int b,int i,int l,int r){
if(r<=a||b<=l){
return 0;
}else if(a<=l&&r<=b){
return v_sum[i];
}else{
int sum_l=gettot(a,b,i*2+1,l,(l+r)/2);
int sum_r=gettot(a,b,i*2+2,(l+r)/2,r);
return sum_l+sum_r;
}
}
void out(int size){
for(int i=n-1;i<size+n;i++){
cout<<v_max[i]<<" ";
}
cout<<"\n";
}
};
int main(){
int n,m,a,b;
cin>>n>>m;
seg st(n);
string query;
for(int i=0;i<m;i++){
cin>>query>>a>>b;
if(query=="update") st.update(a,b);
else if(query=="add") st.add(a,b);
else if(query=="getMin") cout<<st.getMin(a,b)<<"\n";
else if(query=="getMax") cout<<st.getMax(a,b)<<"\n";
else if(query=="getSum") cout<<st.getSum(a,b)<<"\n";
}
//st.out(n);
return 0;
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 ei2113
投稿日時 2021-12-22 17:56:23
言語 C++17
状態 Accepted
得点 1
ソースコード長 3538 Byte
最大実行時間 203 ms
最大メモリ使用量 12248 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 39 ms 604 KB
1
in02 AC 139 ms 956 KB
1
in03 AC 109 ms 7136 KB
1
in04 AC 154 ms 7356 KB
1
in05 AC 51 ms 7184 KB
1
in06 AC 82 ms 4328 KB
1
in07 AC 95 ms 4544 KB
1
in08 AC 175 ms 3216 KB
1
in09 AC 156 ms 8036 KB
1
in10 AC 180 ms 5184 KB
1
in11 AC 51 ms 3732 KB
1
in12 AC 75 ms 2412 KB
1
in13 AC 148 ms 8716 KB
1
in14 AC 203 ms 4452 KB
1
in15 AC 110 ms 9152 KB
1
in16 AC 151 ms 3988 KB
1
in17 AC 137 ms 9836 KB
1
in18 AC 65 ms 9800 KB
1
in19 AC 139 ms 10012 KB
1
in20 AC 84 ms 9976 KB
1
in21 AC 103 ms 7112 KB
1
in22 AC 170 ms 7448 KB
1
in23 AC 127 ms 10732 KB
1
in24 AC 134 ms 7876 KB
1
in25 AC 159 ms 6560 KB
1
in26 AC 172 ms 11388 KB
1
in27 AC 159 ms 11736 KB
1
in28 AC 194 ms 8876 KB
1
in29 AC 64 ms 12032 KB
1
in30 AC 162 ms 12248 KB
1
in31 AC 101 ms 9392 KB
1
in32 AC 153 ms 9612 KB
1