제출 #366907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366907		SeDunion	Strange Device (APIO19_strange_device)	C++17	100 / 100	782 ms	39692 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

int n; ll A, B;

vector<pair<ll,ll>> v;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> A >> B;
	ll g = gcd(A, B + 1), I;
	if (A / g > ll(2e18) / B) {
		I = ll(2e18);
	} else {
		I = A * B / g;
	}
	for (int i = 1 ; i <= n ; ++ i) {
		ll l, r;
		cin >> l >> r;
		if (r - l + 1 >= I) {
			cout << I << "\n";
			return 0;
		}
		ll L = l % I, R = r % I;
		if (L <= R) {
			v.emplace_back(L, +1);
			v.emplace_back(R + 1, -1);
		} else {
			v.emplace_back(0, +1);
			v.emplace_back(R + 1, -1);
			v.emplace_back(L, +1);
			v.emplace_back(I, -1);
		}
	}
	sort(v.begin(), v.end());
	ll k = 0, l = -1, Ans = 0;
	for (auto [i, t] : v) {
		if (t == +1) {
			if (k++ == 0) l = i;
		} else if (--k == 0) Ans += i - l, l = i;
	}
	cout << Ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30