結果

問題 No.1036 Make One With GCD 2
コンテスト
ユーザー simkaren
提出日時 2020-05-30 15:55:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,878 bytes
コンパイル時間 3,049 ms
コンパイル使用メモリ 201,012 KB
実行使用メモリ 25,856 KB
最終ジャッジ日時 2024-11-07 18:40:01
合計ジャッジ時間 11,912 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

inline ll gcd(ll a, ll b){
    if (b > a) return gcd(b, a);
    if (b == 0) return a;
    return gcd(b, a % b);
}

template<typename T>
struct SegmentTree {
private:
	int sz, n;
	vector<T> data;
	function<T(T, T)> f;
	T identity_element;
public:
	/* constructor */
	SegmentTree(
		vector<T>& v, // initial data
		T identity_element, // identity element
		function<T(T, T)> f // operation
	) {
		sz = v.size();
		n = 1; while (n < sz) n <<= 1;
		this->f = f;
		this->identity_element = identity_element;
		data.resize(2 * n - 1, identity_element);
		for (int i = 0; i < sz; ++i)
			data[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; --i)
			data[i] = f(data[2 * i + 1], data[2 * i + 2]);
	}
	/* update query */
	void update(int idx, const T val) {
		idx += n - 1;
		data[idx] = val;
		while (idx) {
			idx = (idx - 1) >> 1;
			data[idx] = f(data[2 * idx + 1], data[2 * idx + 2]);
		}
	}
	/* get query */
	T get(int left, int right, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		if (r <= left || right <= l) return identity_element;
		if (left <= l && r <= right) return data[k];
		T val_l = get(left, right, 2 * k + 1, l, (l + r) / 2);
		T val_r = get(left, right, 2 * k + 2, (l + r) / 2, r);
		return f(val_l, val_r);
	}
};

int main(void){
	int N; cin >> N;
	vector<ll> A(N);
	for (int i = 0; i < N; ++i)
		cin >> A[i];
	SegmentTree<ll> seg(
		A, 0LL, [](ll a, ll b){
			return gcd(a, b);
		}
	);
	ll res = 0;
	for (int i = 0; i < N; ++i){
		if (seg.get(i, N) > 1) continue;
		if (A[i] == 1){
			res += N - i;
			continue;
		}
		int ng = i + 1, ok = N;
		while (ok - ng > 1){
			int mid = (ok + ng) / 2;
			if (seg.get(i, mid) > 1) ng = mid;
			else ok = mid;
		}
		res += N - ok + 1;
	}
	cout << res << endl;
    return 0;
}
0