Submission #74748

ソースコード

?
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
/**********************
* *
* セグ木テンプレ *
* *
**********************/
//1072 - セグメントツリー技術基礎
//参考 - ei2009
#include<bits/stdc++.h>
#define rep(i,a,n) for(long long i=a;i<n;i++)
#define repp(i,a,n) for(long long i=a;i>=n;i--)
#define so(z) sort(z.begin(),z.end())
#define sor(z) sort(z.rbegin(),z.rend())
#define re(z) reverse(z.begin(),z.end())
#define su(a) substr(a)
#define sub(a,b) substr(a,b)
#define yess cout<<"YES"<<nn
#define noo cout<<"NO"<<nn
#define yes cout<<"Yes"<<"\n"
#define no cout<<"No"<<"\n"
#define yesr cout<<"Yes"<<"\n";return(0)
#define nor cout<<"No"<<"\n";return(0)
#define fi first
#define se second
#define fr() front()
#define mp make_pair
#define pb push_back
#define nn "\n"
#define ll long long
#define mod 1000000007
#define IM INT_MAX
#define LM LONG_LONG_MAX
#define gcd(x,y) __gcd(x,y) //最大公約数
#define lcm(x,y) x/(__gcd(x,y))*y //最小公倍数
#define prev(a) prev_permutation(a.begin(),a.end()) //辞書前
#define next(a) next_permutation(a.begin(),a.end()) //辞書後
#define get(s) getline(cin,s) //　空白の空いたstringの入力
#define fixed(a) fixed<<setprecision(a) //小数点何桁か指定
#define ro(a) round(a) //四捨五入
#define ce(a) ceil(a) //切り上げ
#define up(a,v) upper_bound(a.begin(),a.end(),v)
#define lo(a,v) lower_bound(a.begin(),a.end(),v)
#define bi(a,v) binary_bound(a.begin(),a.end(),v)
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;
}
}
//出力用コード(最大値ver.)
void out(int size){
for(int i=n-1;i<size+n;i++){
cout<<v_sum[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 - セグメントツリー技術基礎
ユーザー名 r2201
投稿日時 2023-07-21 14:30:52
言語 C++17
状態 Accepted
得点 1
ソースコード長 4728 Byte
最大実行時間 222 ms
最大メモリ使用量 39024 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 45 ms 600 KB
1
in02 AC 154 ms 1976 KB
1
in03 AC 110 ms 8672 KB
1
in04 AC 160 ms 10044 KB
1
in05 AC 54 ms 10264 KB
1
in06 AC 82 ms 7796 KB
1
in07 AC 102 ms 8656 KB
1
in08 AC 172 ms 8744 KB
1
in09 AC 168 ms 14592 KB
1
in10 AC 174 ms 13272 KB
1
in11 AC 45 ms 11948 KB
1
in12 AC 75 ms 11272 KB
1
in13 AC 162 ms 18344 KB
1
in14 AC 204 ms 15740 KB
1
in15 AC 115 ms 21328 KB
1
in16 AC 157 ms 17192 KB
1
in17 AC 172 ms 23808 KB
1
in18 AC 74 ms 24412 KB
1
in19 AC 142 ms 25400 KB
1
in20 AC 92 ms 26128 KB
1
in21 AC 151 ms 23916 KB
1
in22 AC 217 ms 25660 KB
1
in23 AC 136 ms 29716 KB
1
in24 AC 138 ms 27884 KB
1
in25 AC 158 ms 27840 KB
1
in26 AC 200 ms 33940 KB
1
in27 AC 158 ms 35308 KB
1
in28 AC 222 ms 34116 KB
1
in29 AC 66 ms 37528 KB
1
in30 AC 182 ms 39024 KB
1
in31 AC 102 ms 36808 KB
1
in32 AC 158 ms 38180 KB
1