Submission #58526

ソースコード

?
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<int> value;
segmenttreesum(int n){
N=1;
while(N<n){
N*=2;
}
value=vector<int>(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]);
}
}
int 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<int> value;
segmenttreemax(int n){
N=1;
while(N<n){
N*=2;
}
value=vector<int>(2*N-1,-99999999);
}
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]);
}
}
int query(int a,int b,int k,int l,int r){
if(r<=a || b<=l){
return -99999999;
}
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<int> value;
segmenttreemin(int n){
N=1;
while(N<n){
N*=2;
}
value=vector<int>(2*N-1,INF);
}
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]);
}
}
int query(int a,int b,int k,int l,int r){
if(r<=a || b<=l){
return INF;
}
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:53:23
言語 C++14
状態 Accepted
得点 1
ソースコード長 3152 Byte
最大実行時間 190 ms
最大メモリ使用量 9104 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01 AC 25 ms 600 KB
1
in02 AC 137 ms 952 KB
1
in03 AC 102 ms 4024 KB
1
in04 AC 164 ms 4116 KB
1
in05 AC 48 ms 4072 KB
1
in06 AC 83 ms 2752 KB
1
in07 AC 107 ms 2968 KB
1
in08 AC 178 ms 2540 KB
1
in09 AC 149 ms 4932 KB
1
in10 AC 181 ms 3736 KB
1
in11 AC 46 ms 2924 KB
1
in12 AC 75 ms 2248 KB
1
in13 AC 152 ms 5580 KB
1
in14 AC 190 ms 3744 KB
1
in15 AC 111 ms 6136 KB
1
in16 AC 159 ms 3664 KB
1
in17 AC 138 ms 6444 KB
1
in18 AC 74 ms 6660 KB
1
in19 AC 146 ms 6756 KB
1
in20 AC 85 ms 6840 KB
1
in21 AC 101 ms 5516 KB
1
in22 AC 177 ms 5864 KB
1
in23 AC 124 ms 7616 KB
1
in24 AC 141 ms 6300 KB
1
in25 AC 160 ms 5744 KB
1
in26 AC 179 ms 8388 KB
1
in27 AC 163 ms 8604 KB
1
in28 AC 189 ms 7396 KB
1
in29 AC 69 ms 8892 KB
1
in30 AC 162 ms 9104 KB
1
in31 AC 102 ms 7656 KB
1
in32 AC 152 ms 7996 KB
1