結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:01:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,643 ms / 2,000 ms |
コード長 | 3,430 bytes |
コンパイル時間 | 3,136 ms |
コンパイル使用メモリ | 199,904 KB |
最終ジャッジ日時 | 2025-01-09 23:48:14 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>#define all(vec) vec.begin(), vec.end()#define pb push_back#define eb emplace_back#define fi first#define se secondusing namespace std;using ll = long long;using P = pair<ll, ll>;template <class T>using V = vector<T>;constexpr ll INF = (1LL << 30) - 1LL;constexpr ll MOD = 998244353LL;constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};template <class T>void chmin(T &a, T b) { a = min(a, b); }template <class T>void chmax(T &a, T b) { a = max(a, b); }void debug() { cerr << "ok" << endl; }template <class T>void printv(const vector<T> &v) {for (int i = 0; i < v.size(); i++) cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');}template <class T>void readv(vector<T> &v) {for (int i = 0; i < v.size(); i++) cin >> v[i];}//Point Update Range Gettemplate <class T>struct Segtree {int n;vector<T> dat;Segtree(int n_) {n = 1;while (n < n_) {n <<= 1;}dat.resize(2 * n, T::e);}Segtree(int n_, const vector<T> &a) {n = 1;while (n < n_) {n <<= 1;}dat.resize(2 * n, T::e);for (int i = 0; i < a.size(); i++) {dat[i + n] = a[i];}for (int i = n - 1; i > 0; i--) {dat[i] = T::f(dat[i << 1], dat[i << 1 | 1]);}}void upd(int k, const T &x) {k += n;T::g(dat[k], x);k >>= 1;while (k > 0) {dat[k] = T::f(dat[k << 1], dat[k << 1 | 1]);k >>= 1;}}T get(const int &a, const int &b, int k, int l, int r) {if (b <= l || r <= a) {return T::e;}if (a <= l && r <= b) {return dat[k];}return T::f(get(a, b, k << 1, l, (l + r) >> 1),get(a, b, k << 1 | 1, (l + r) >> 1, r));}inline T get(const int &a, const int &b) { //[a,b)if (a >= b) {return T::e;}return get(a, b, 1, 0, n);}int find(const int &a, const int &b, const T &x, int k, int l, int r) {if (b <= l || r <= a || dat[k] > x) {return -1;}if (k >= n) {return k - n;}int il = find(a, b, x, k << 1, l, (l + r) >> 1);if (il != -1) {return il;}return find(a, b, x, k << 1 | 1, (l + r) >> 1, r);}inline int find(const int &a, const int &b, const T &x) { //[a,b)における、値<=x なる最左のindexを求めるif (a >= b) {return -1;}return find(a, b, x, 1, 0, n);}};struct T {ll a;inline static T f(const T &x, const T &y) {if (x.a == -1) return y;if (y.a == -1) return x;return T{__gcd(x.a, y.a)};}inline static void g(T &a, const T &b) {a = b;}static T e;};T T::e = T{-1};int main() {ios::sync_with_stdio(0);cin.tie(0);int n;cin >> n;Segtree<T> seg(n);for (int i = 0; i < n; i++) {ll a;cin >> a;seg.upd(i, T{a});}int r = 0;ll res = 0;for (int l = 0; l < n; l++) {chmax(r, l);while (r < n && seg.get(l, r + 1).a > 1) {r++;}res += n - r;// cout << l << " " << r << " " << seg.get(l, r + 1).a << endl;}cout << res << '\n';}