Submission #81723

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
template<typename T>
struct seg{
T shoki;
function<T(T,T)>f;
vector< T >s;
int sz;
seg(int n,function<T(T,T)>F,T sh = 0){
shoki = sh;
f = F;
sz = 1;
while(sz < n)sz*=2;
s.resize(2*sz,shoki);
}
seg(vector< T > x,function<T(T,T)>F,T sh = 0):seg(x.size(),F,sh){
for(int i = 0;i < x.size();i++){
s[sz-1+i] = x[i];
}
for(int i = sz-2;i >= 0;i--){
s[i] = f(s[2*i+1],s[2*i+2]);
}
}
T q(int a,int b,int k,int l,int r){
if(r <= a||b <= l)return shoki;
if(a <= l&&r <= b)return s[k];
return f(q(a,b,2*k+1,l,(l+r)/2),q(a,b,2*k+2,(l+r)/2,r));
}
T q(int a,int b){
return q(a,b,0,0,sz);
}
void update(int k,T x){
k += sz-1;
s[k] = x;
while(k > 0){
k = (k-1)/2;
s[k] = f(s[2*k+1],s[2*k+2]);
}
}
void debug(){
cout <<"-----------------\n";
for(int i = 0,x = 2;i < sz*2-1;i++){
cout << s[i] <<" ";
if(x-2 == i){
x *= 2;
cout << "\n";
}
}
cout <<"-----------------\n";
}
};
int main(){
//string ss;cin >>ss;
//ifstream ifs("io/input"+ss+".txt");
//ofstream ofs("io/output"+ss+".txt");
//#define cin ifs
//#define cout ofs
int n;
cin >>n;
vector<int>A(n);
for(int i = 0;i < n;i++){
cin >>A[i];
}
seg<int> st(A,[](int x,int y){
if(min(x,y) == 0)return max(x,y);
return gcd(x,y);
},0);
int q;
cin >>q;
while(q--){
int x,a,b;
cin >>x>>a>>b;
// st.debug();
if(x == 1){
st.update(a-1,b);
}else{
cout <<st.q(a-1,b)<<"\n";
}
}
}

ステータス

項目 データ
問題 1905 - GCD
ユーザー名 ei2332
投稿日時 2024-11-19 21:33:43
言語 C++17
状態 Accepted
得点 7
ソースコード長 1958 Byte
最大実行時間 226 ms
最大メモリ使用量 2460 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input1.txt AC 27 ms 604 KB
1
input2.txt AC 29 ms 660 KB
1
input3.txt AC 15 ms 628 KB
1
input4.txt AC 23 ms 600 KB
1
input5.txt AC 21 ms 704 KB
1
input6.txt AC 21 ms 680 KB
1
input7.txt AC 25 ms 652 KB
1
input8.txt AC 63 ms 752 KB
1
input9.txt AC 226 ms 2460 KB
1
input10.txt AC 171 ms 2116 KB
1