Submission #58525

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
#define INF 2147483647 // 2^31-1
struct segmenttreesum{
int N;
vector<long long> value;
segmenttreesum(int n){
N=1;
while(N<n){
N*=2;
}
value=vector<long long>(2*N-1,0);
}
void update(int i,int x){
i+=N-1;
value[i]=x;
while(i>0){
i=(i-1)/2;
value[i]=(value[i*2+1]+value[i*2+2]);
}
}
void add(int i,int x){
i+=N-1;
value[i]+=x;
while(i>0){
i=(i-1)/2;
value[i]=(value[i*2+1]+value[i*2+2]);
}
}
long long query(int a,int b,int k,int l,int r){
if(r<=a || b<=l){
return 0;
}
else if(a<=l && r<=b){
return value[k];
}
else{
int c1=query(a,b,2*k+1,l,(l+r)/2);
int c2=query(a,b,2*k+2,(l+r)/2,r);
return (c1+c2);
}
}
};
struct segmenttreemax{
int N;
vector<long long> value;
segmenttreemax(int n){
N=1;
while(N<n){
N*=2;
}
value=vector<long long>(2*N-1,-9999999999);
}
void update(int i,int x){
i+=N-1;
value[i]=x;
while(i>0){
i=(i-1)/2;
value[i]=max(value[i*2+1],value[i*2+2]);
}
}
void add(int i,int x){
i+=N-1;
value[i]+=x;
while(i>0){
i=(i-1)/2;
value[i]=max(value[i*2+1],value[i*2+2]);
}
}
long long query(int a,int b,int k,int l,int r){
if(r<=a || b<=l){
return -9999999999;
}
else if(a<=l && r<=b){
return value[k];
}
else{
int c1=query(a,b,2*k+1,l,(l+r)/2);
int c2=query(a,b,2*k+2,(l+r)/2,r);
return max(c1,c2);
}
}
};
struct segmenttreemin{
int N;
vector<long long> value;
segmenttreemin(int n){
N=1;
while(N<n){
N*=2;
}
value=vector<long long>(2*N-1,9999999999);
}
void update(int i,int x){
i+=N-1;
value[i]=x;
while(i>0){
i=(i-1)/2;
value[i]=min(value[i*2+1],value[i*2+2]);
}
}
void add(int i,int x){
i+=N-1;
value[i]+=x;
while(i>0){
i=(i-1)/2;
value[i]=min(value[i*2+1],value[i*2+2]);
}
}
long long query(int a,int b,int k,int l,int r){
if(r<=a || b<=l){
return 9999999999;
}
else if(a<=l && r<=b){
return value[k];
}
else{
int c1=query(a,b,2*k+1,l,(l+r)/2);
int c2=query(a,b,2*k+2,(l+r)/2,r);
return min(c1,c2);
}
}
};
int main(){
int n,m;
cin>>n>>m;
segmenttreesum sgsum(n);
segmenttreemax sgmax(n);
segmenttreemin sgmin(n);
int x,y;
string s;
for(int i=0;i<n;i++){
sgsum.update(i,0);
sgmin.update(i,0);
sgmax.update(i,0);
}
for(int i=0;i<m;i++){
cin>>s>>x>>y;
if(s[0]=='u'){
sgsum.update(x,y);
sgmin.update(x,y);
sgmax.update(x,y);
}
else if(s[0]=='a'){
sgsum.add(x,y);
sgmin.add(x,y);
sgmax.add(x,y);
}
else if(s[3]=='S'){
cout<<sgsum.query(x,y,0,0,sgsum.N)<<'\n';
}
else if(s[3]=='M' && s[4]=='a'){
cout<<sgmax.query(x,y,0,0,sgmax.N)<<'\n';
}
else{
cout<<sgmin.query(x,y,0,0,sgmin.N)<<'\n';
}
}
return(0);
}

ステータス

項目 データ
問題 1072 - セグメントツリー技術基礎
ユーザー名 ei1918
投稿日時 2020-02-07 14:51:30
言語 C++14
状態 Accepted
得点 1
ソースコード長 3224 Byte
最大実行時間 194 ms
最大メモリ使用量 12156 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 35 ms 604 KB
1
in02 AC 134 ms 1084 KB
1
in03 AC 113 ms 7140 KB
1
in04 AC 149 ms 7228 KB
1
in05 AC 49 ms 7196 KB
1
in06 AC 79 ms 4340 KB
1
in07 AC 103 ms 4428 KB
1
in08 AC 176 ms 3240 KB
1
in09 AC 145 ms 8192 KB
1
in10 AC 182 ms 5204 KB
1
in11 AC 46 ms 3756 KB
1
in12 AC 74 ms 2564 KB
1
in13 AC 156 ms 8616 KB
1
in14 AC 192 ms 4484 KB
1
in15 AC 112 ms 9184 KB
1
in16 AC 157 ms 4024 KB
1
in17 AC 144 ms 9616 KB
1
in18 AC 75 ms 9704 KB
1
in19 AC 149 ms 9916 KB
1
in20 AC 89 ms 10004 KB
1
in21 AC 108 ms 7144 KB
1
in22 AC 187 ms 7356 KB
1
in23 AC 125 ms 10648 KB
1
in24 AC 138 ms 7792 KB
1
in25 AC 149 ms 6600 KB
1
in26 AC 194 ms 11428 KB
1
in27 AC 160 ms 11644 KB
1
in28 AC 183 ms 8912 KB
1
in29 AC 66 ms 12072 KB
1
in30 AC 161 ms 12156 KB
1
in31 AC 106 ms 9300 KB
1
in32 AC 163 ms 9640 KB
1