Submission #68001


ソースコード

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <bits/stdc++.h>
//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (n - 1); i > (a - 1); --i)
#define arep(i, x) for (auto&& i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define Unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define updiv(a, b) ((a + b - 1) / b)
#define cauto const auto&
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T> //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T> //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) { //多次元初期化
std::fill((T*)array, (T*)(array + N), val);
}
template <class A, class B>
bool chmax(A& a, const B& b) { //最大値更新 返り値はbool
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class A, class B>
bool chmin(A& a, const B& b) { //最小値更新 返り値はbool
if (b < a) {
a = b;
return 1;
}
return 0;
}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, 1, -1, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END
/*
SegmentTree(n,f,M1):
サイズnで初期化、fは2つの区間の要素をマージする二項演算、
M1はモノイドの単位元。
set(k,x): k番目の要素にxを代入。
build(): セグメント木を一気に構築する。 O(n)
update(k,x): k番目の要素をxに変更。 O(log(n))
query(a,b): 区間[a,b)にfを作用させた値を取得。 O(log(n))
operator[k]: k番目の要素を返す。 O(log(n))
find_first(a,check): [a,x)がcheck以上の最初の位置xを返す。 O(log(n))
find_last(a,check): [x,b)がcheck以上の最後の位置xを返す。 O(log(n))
*/
template <typename Monoid>
struct SegmentTree {
using F = function<Monoid(Monoid, Monoid)>;
int sz;
vector<Monoid> seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
sz = 1;
while (sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) { seg[k + sz] = x; }
void build() {
for (int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while (k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if (a & 1) L = f(L, seg[a++]);
if (b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const { return seg[k + sz]; }
template <typename C>
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while (a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if (check(nxt))
a = 2 * a + type;
else
M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template <typename C>
int find_first(int a, const C &check) {
Monoid L = M1;
if (a <= 0) {
if (check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return -1;
}
int b = sz;
for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if (a & 1) {
Monoid nxt = f(L, seg[a]);
if (check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template <typename C>
int find_last(int b, const C &check) {
Monoid R = M1;
if (b >= sz) {
if (check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for (b += sz; a < b; a >>= 1, b >>= 1) {
if (b & 1) {
Monoid nxt = f(seg[--b], R);
if (check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
signed main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
SegmentTree<int> seg(n,[](int a,int b) {return gcd(a,b);}, 0);
rep(i,0,n){
int a;
cin>>a;
seg.set(i,a);
}
seg.build();
rep(i,0,q){
int t,x,y;
cin>>t>>x>>y;
if(t == 1){
seg.update(x-1, y);
}else{
int g = seg.query(x-1, y);
int ans = 0;
for(int i = 1; i * i <= g; ++i){
if(g%i==0){
ans+=i;
if(i*i!=g) ans+=g/i;
}
}
cout<<ans<<'\n';
}
}
return 0;
}

ステータス

項目 データ
問題 1516 - 『公約数』総和企画
ユーザー名 immunity
投稿日時 2021-08-05 11:07:22
言語 C++17
状態 Time Limit Exceeded
得点 0
ソースコード長 5340 Byte
最大実行時間 500 ms
最大メモリ使用量 14324 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 76 ms 4700 KB
1
in02.txt AC 44 ms 4776 KB
1
in03.txt AC 129 ms 4976 KB
1
in04.txt AC 87 ms 5052 KB
1
in05.txt AC 128 ms 5256 KB
1
in06.txt AC 68 ms 5204 KB
1
in07.txt AC 106 ms 5276 KB
1
in08.txt AC 101 ms 2020 KB
1
in09.txt AC 85 ms 3628 KB
1
in10.txt AC 67 ms 5748 KB
1
in11.txt AC 39 ms 2752 KB
1
in12.txt AC 58 ms 2436 KB
1
in13.txt AC 92 ms 4172 KB
1
in14.txt AC 55 ms 4368 KB
1
in15.txt AC 51 ms 6616 KB
1
in16.txt AC 46 ms 4516 KB
1
in17.txt AC 71 ms 2796 KB
1
in18.txt AC 56 ms 3124 KB
1
in19.txt AC 135 ms 7676 KB
1
in20.txt AC 128 ms 8008 KB
1
in21.txt TLE 500 ms 8972 KB
1
in22.txt TLE 500 ms 9808 KB
1
in23.txt TLE 500 ms 10520 KB
1
in24.txt TLE 500 ms 11228 KB
1
in25.txt TLE 500 ms 12068 KB
1
in26.txt TLE 500 ms 12780 KB
1
in27.txt TLE 500 ms 13488 KB
1
in28.txt TLE 500 ms 14324 KB
1
sample.txt AC 29 ms 10296 KB
1