Submission #78756

ソースコード

?
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
#if !__INCLUDE_LEVEL__
#include __FILE__
//----------------------------------------
//名前　segtree
//仕様 初期宣言(要素数,更新関数,初期値(ない場合は0))
// セグ木を生成する
//
// rmq(範囲開始,範囲末尾)
// 範囲内探索を行う
//
// update(更新場所,更新後の値)
// 一点更新を行う
//----------------------------------------
template<typename T>
class B_segtree{
vector<T>seg;
int sz;
T x;
T (*f)(T,T);
public: virtual void maketree(int n,T (*p)(T,T),T y = 0){
sz = 1;
while(sz < n)sz <<= 1;
x = y;
f = p;
seg.resize(2*sz-1,x);
if(f(y,y) != y){
for(int i = sz-2;i >= 0;i--){
seg[i] = f(seg[2*i+1],seg[2*i+2]);
}
}
}
public:T rmq(int a,int b,int k,int l,int r){
if(a >= r||b <= l)return x;
if(a <= l&&r <= b)return(seg[k]);
return f(rmq(a,b,2*k+1,l,(l+r)>>1),
rmq(a,b,2*k+2,(l+r)>>1,r));
}
public:T rmq(int a,int b){
return rmq(a,b,0,0,sz);
}
public:void update(int k,T y){
k += sz-1;
seg[k] = y;
while(k > 0){
k = (k-1)>>1;
seg[k] = f(seg[2*k+1],seg[2*k+2]);
}
}
public:void operation(int k,T (*p)(T)){
k += sz-1;
seg[k] = p(seg[k]);
while(k > 0){
k = (k-1)>>1;
seg[k] = f(seg[2*k+1],seg[2*k+2]);
}
}
};
template<typename S>
class segtree :public B_segtree<S>{
public:segtree(int n,S (*p)(S,S),S y = 0){
this->maketree(n,p,y);
}
};
main(){
start();
int n;
cin >>n;
segtree<int> tree(n,[](int x,int y){return min(x,y);},INF);//セグ木の作成
for(int i = 0;i < n;i++){
int x;
cin >>x;
tree.update(i,x);//値の更新（i番目をxに設定）
}
queue<int>ans;
while(1){
string s;
int x,y;
cin >>s;
if(s == "min"){//min値の出力
cin >>x>>y;
ans.push(tree.rmq(x,y+1));//min値の出力はxは含む、yは含まず。
}else if(s == "update"){//値の更新
cin >>x>>y;
tree.update(x,y);
}else{
break;
}
}
queue<int>debug = ans;
while(!debug.empty()){
cout <<debug.front()<<endl;
debug.pop();
}
}
#else
#include<bits/stdc++.h>
#define endl "\n"
#define INF LONG_LONG_MAX
#define rpqueue(i) priority_queue<i>
#define pqueue(i) priority_queue<i,vector<i>,greater<i>>
#define yn(i) if(i)cout<<"Yes\n";else cout<<"No\n"
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define all(i) i.begin(),i.end()
#define loop(i,s,e) for(int i = s;i < e;i++)
#define rloop(i,s,e) for(int i = s;i >= e;i--)
#define int long long
#define vec vector
using namespace std;
void start(){
cin.tie(nullptr);ios::sync_with_stdio(false);
cout << std::fixed << std::setprecision(10);
}
long long modinv(long long a,long long m){
long long b = m,u = 1,v = 0;
while(b){
long long t = a / b;
a -= t * b;swap(a,b);
u -= t * v;swap(u,v);
}
u %= m;
if(u < 0)u += m;
return u;
}
bool isPrime(long long x) {
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
#endif

ステータス

項目 データ
問題 0459 - セグメントツリー練習
ユーザー名 ei2332
投稿日時 2024-05-10 22:49:17
言語 C++17
状態 Accepted
得点 10
ソースコード長 3162 Byte
最大実行時間 41 ms
最大メモリ使用量 2752 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
Input01 AC 32 ms 604 KB
1
Input02 AC 15 ms 428 KB
1
Input03 AC 19 ms 508 KB
1
Input04 AC 22 ms 588 KB
1
Input05 AC 25 ms 532 KB
1
Input06 AC 21 ms 612 KB
1
Input07 AC 21 ms 548 KB
1
Input08 AC 19 ms 620 KB
1
Input09 AC 20 ms 788 KB
1
Input10 AC 41 ms 2752 KB
1