#494410 (C++17) No.1036 Make One With GCD 2

• 問題: No.1036 Make One With GCD 2
• ユーザー: kya_ski
• 提出日時: 2020-06-09 17:20:36
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 509 ms / 2,000 ms
• コード長: 1,865 bytes
• コンパイル時間: 3,880 ms
• コンパイル使用メモリ: 207,688 KB
• 実行使用メモリ: 15,856 KB
• 最終ジャッジ日時: 2023-10-14 20:33:45
• 合計ジャッジ時間: 16,004 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	346 ms; 7,520 KB
testcase_01	AC	306 ms; 7,220 KB
testcase_02	AC	352 ms; 15,696 KB
testcase_03	AC	31 ms; 4,380 KB
testcase_04	AC	52 ms; 5,604 KB
testcase_05	AC	2 ms; 4,352 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	107 ms; 4,560 KB
testcase_08	AC	88 ms; 4,480 KB
testcase_09	AC	306 ms; 7,032 KB
testcase_10	AC	285 ms; 6,528 KB
testcase_11	AC	311 ms; 6,964 KB
testcase_12	AC	287 ms; 6,812 KB
testcase_13	AC	504 ms; 6,680 KB
testcase_14	AC	509 ms; 7,052 KB
testcase_15	AC	476 ms; 6,564 KB
testcase_16	AC	481 ms; 6,788 KB
testcase_17	AC	496 ms; 6,648 KB
testcase_18	AC	2 ms; 4,348 KB
testcase_19	AC	2 ms; 4,356 KB
testcase_20	AC	3 ms; 4,348 KB
testcase_21	AC	3 ms; 4,352 KB
testcase_22	AC	468 ms; 6,456 KB
testcase_23	AC	346 ms; 5,800 KB
testcase_24	AC	489 ms; 6,788 KB
testcase_25	AC	446 ms; 6,148 KB
testcase_26	AC	461 ms; 6,496 KB
testcase_27	AC	1 ms; 4,348 KB
testcase_28	AC	1 ms; 4,352 KB
testcase_29	AC	1 ms; 4,356 KB
testcase_30	AC	1 ms; 4,348 KB
testcase_31	AC	1 ms; 4,352 KB
testcase_32	AC	2 ms; 4,352 KB
testcase_33	AC	2 ms; 4,352 KB
testcase_34	AC	2 ms; 4,352 KB
testcase_35	AC	2 ms; 4,352 KB
testcase_36	AC	2 ms; 4,352 KB
testcase_37	AC	2 ms; 4,348 KB
testcase_38	AC	337 ms; 15,856 KB
testcase_39	AC	363 ms; 6,960 KB
testcase_40	AC	346 ms; 5,772 KB
testcase_41	AC	397 ms; 7,204 KB
testcase_42	AC	398 ms; 6,956 KB
testcase_43	AC	396 ms; 9,280 KB
testcase_44	AC	399 ms; 8,052 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

template<class T>
struct queue_aggregation {
	using F = function<T(T, T)>;
	using value_type = T;
private : 
	struct node {
		value_type val, sum;
		node (const value_type &val, const value_type &sum) : val(val), sum(sum) { }
	};
	const F f;
	stack<node> front_stack, back_stack;

public : 
	queue_aggregation (const F &f) : f(f), front_stack(), back_stack() { }

	constexpr bool empty () const noexcept {
		return (front_stack.empty() and back_stack.empty());
	}

	constexpr size_t size () const noexcept {
		return (front_stack.size() + back_stack.size());
	}

	void push (const value_type &x) {
		if (back_stack.empty()) {
			back_stack.emplace(x, x);
		} else {
			value_type s = f(back_stack.top().sum, x);
			back_stack.emplace(x, s);
		}
	}

	void pop () {
		assert(not empty());
		if (front_stack.empty()) {
			front_stack.emplace(back_stack.top().val, back_stack.top().val);
			back_stack.pop();
			while (not back_stack.empty()) {
				value_type s = f(back_stack.top().val, front_stack.top().sum);
				front_stack.emplace(back_stack.top().val, s);
				back_stack.pop();
			}
		}
		front_stack.pop();
	}

	value_type fold () {
		assert(not empty());
		if (front_stack.empty()) {
			return (back_stack.top().sum);
		} else if (back_stack.empty()) {
			return (front_stack.top().sum);
		} else {
			return (f(front_stack.top().sum, back_stack.top().sum));
		}
	}

};


int main() {
	int n;
	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	queue_aggregation<long long> que([](long long a, long long b) { return gcd(a, b); });
	
	long long ans = 0;
	for (int l = 0, r = 0; l < n; l++) {
		while ((que.empty() or que.fold() > 1) and r < n) que.push(a[r++]);
		if (not que.empty() and que.fold() == 1) ans += (n - r + 1);
		que.pop();
	}
	
	cout << ans << '\n';
	
	return 0;
}