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
|