#995015 (C++23) No.1036 Make One With GCD 2

提出ソース

結果

問題	No.1036 Make One With GCD 2
ユーザー	kuhaku
提出日時	2024-07-14 17:01:57
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	274 ms / 2,000 ms
コード長	7,190 bytes
コンパイル時間	4,080 ms
コンパイル使用メモリ	268,792 KB
実行使用メモリ	11,144 KB
最終ジャッジ日時	2024-07-14 17:02:13
合計ジャッジ時間	14,243 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	121 ms 7,400 KB
testcase_01	AC	132 ms 6,996 KB
testcase_02	AC	114 ms 11,136 KB
testcase_03	AC	17 ms 6,940 KB
testcase_04	AC	29 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	51 ms 6,940 KB
testcase_08	AC	43 ms 6,944 KB
testcase_09	AC	165 ms 6,984 KB
testcase_10	AC	150 ms 6,944 KB
testcase_11	AC	164 ms 6,976 KB
testcase_12	AC	155 ms 6,940 KB
testcase_13	AC	264 ms 6,944 KB
testcase_14	AC	266 ms 6,968 KB
testcase_15	AC	248 ms 6,940 KB
testcase_16	AC	267 ms 6,944 KB
testcase_17	AC	258 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	3 ms 6,944 KB
testcase_22	AC	244 ms 6,944 KB
testcase_23	AC	179 ms 6,944 KB
testcase_24	AC	274 ms 6,944 KB
testcase_25	AC	266 ms 6,944 KB
testcase_26	AC	246 ms 6,944 KB
testcase_27	AC	1 ms 6,944 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,944 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	113 ms 11,144 KB
testcase_39	AC	144 ms 7,156 KB
testcase_40	AC	188 ms 6,944 KB
testcase_41	AC	151 ms 7,120 KB
testcase_42	AC	147 ms 7,004 KB
testcase_43	AC	143 ms 8,200 KB
testcase_44	AC	151 ms 7,552 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// competitive-verifier: PROBLEM
#include <stack>
#include <algorithm>
#include <limits>
#include <utility>
template <class T>
struct Add {
    using value_type = T;
    static constexpr T id = T(0);
    static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs + rhs;
    }
};
template <class T>
struct Mul {
    using value_type = T;
    static constexpr T id = T(1);
    static constexpr T op(const T &lhs, const T &rhs) { return lhs * rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs * rhs;
    }
};
template <class T>
struct And {
    using value_type = T;
    static constexpr T id = std::numeric_limits<T>::max();
    static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs & rhs;
    }
};
template <class T>
struct Or {
    using value_type = T;
    static constexpr T id = T(0);
    static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs | rhs;
    }
};
template <class T>
struct Xor {
    using value_type = T;
    static constexpr T id = T(0);
    static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs ^ rhs;
    }
};
template <class T>
struct Min {
    using value_type = T;
    static constexpr T id = std::numeric_limits<T>::max();
    static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::min((U)lhs, rhs);
    }
};
template <class T>
struct Max {
    using value_type = T;
    static constexpr T id = std::numeric_limits<T>::min();
    static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return std::max((U)lhs, rhs);
    }
};
template <class T>
struct Update {
    using value_type = T;
    static constexpr T id = std::numeric_limits<T>::max();
    static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id ? rhs : lhs; }
    template <class U>
    static constexpr U f(T lhs, U rhs) {
        return lhs == Update::id ? rhs : lhs;
    }
};
template <class T>
struct Affine {
    using value_type = std::pair<T, T>;
    static constexpr std::pair<T, T> id = std::pair<T, T>(1, 0);
    static constexpr std::pair<T, T> op(std::pair<T, T> lhs, std::pair<T, T> rhs) {
        return {lhs.first * rhs.first, lhs.first * rhs.second + lhs.second};
    }
};
template <class M>
struct Rev {
    using T = typename M::value_type;
    using value_type = T;
    static constexpr T id = M::id;
    static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); }
};
template <class M>
struct sliding_window_aggregation {
  private:
    using T = typename M::value_type;
  public:
    sliding_window_aggregation() : back_total(M::id), front(), back() { front.emplace(M::id); }
    bool empty() const { return front.empty() && back.empty(); }
    int size() const { return front.size() + back.size() - 1; }
    T fold() const { return M::op(back_total, front.top()); }
    void emplace(T val) {
        back.emplace(val);
        back_total = M::op(val, back_total);
    }
    void push(T val) { emplace(val); }
    void pop() {
        if (front.size() == 1) {
            while (!back.empty()) {
                front.emplace(M::op(front.top(), back.top()));
                back.pop();
            }
            back_total = M::id;
        }
        front.pop();
    }
  private:
    T back_total;
    std::stack<T> front, back;
};
#ifdef ATCODER
#pragma GCC target("sse4.2,avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,bmi2")
#endif
#pragma GCC optimize("Ofast,fast-math,unroll-all-loops")
#include <bits/stdc++.h>
#ifndef ATCODER
#pragma GCC target("sse4.2,avx2,bmi2")
#endif
template <class T, class U>
constexpr bool chmax(T &a, const U &b) {
    return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
constexpr bool chmin(T &a, const U &b) {
    return (T)b < a ? a = (T)b, true : false;
}
constexpr std::int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr double EPS = 1e-7;
constexpr double PI = 3.14159265358979323846;
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
struct Sonic {
    Sonic() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(20);
    }
    constexpr void operator()() const {}
} sonic;
using namespace std;
using ll = std::int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &i : v) is >> i;
    return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto it = v.begin(); it != v.end(); ++it) os << (it == v.begin() ? "" : " ") << *it;
    return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
    else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
    else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes\n" : "No\n"); }
void No(bool is_not_correct = true) { Yes(!is_not_correct); }
void YES(bool is_correct = true) { std::cout << (is_correct ? "YES\n" : "NO\n"); }
void NO(bool is_not_correct = true) { YES(!is_not_correct); }
void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; }
void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); }
template <class T>
struct Gcd {
    using value_type = T;
    static constexpr T id = std::numeric_limits<T>::max();
    static constexpr T op(const T &lhs, const T &rhs) {
        return lhs == Gcd::id ? rhs : (rhs == Gcd::id ? lhs : std::gcd(lhs, rhs));
    }
};
int main(void) {
    int n;
    cin >> n;
    vector<ll> a(n);
    cin >> a;
    sliding_window_aggregation<Gcd<ll>> swag;
    ll ans = 0;
    rep (i, n) {
        swag.emplace(a[i]);
        while (!swag.empty() && swag.fold() == 1) swag.pop();
        ans += i + 1 - swag.size();
    }
    co(ans);
    return 0;
}

yukicoder

結果

テストケース

ソースコード