제출 #447198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447198		Ya_Ali	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	598 ms	53260 KiB

strange_device

/* ** *** In the name of God *** ** */
// Only Haider is Amir al-Momenin
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 1;
// #define endl '\n'
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
 
	ll n, A, B;
	cin >> n >> A >> B;
	ll x = 1ll * A / __gcd(A, B + 1);
	if (x <= inf / B) x *= B;
	else x = inf;
	vector<pair<ll, ll>> b;
	while (n--) {
		ll l, r;
		cin >> l >> r;
		if (r - l + 1 >= x) return cout << x, 0;
		l %= x, r %= x;
		if (r >= l) b.push_back({l, r});
		else b.push_back({l, x - 1}), b.push_back({0, r});
	}
	sort(b.begin(), b.end());
	ll p = 0, ans = x;
	for (auto i : b) {
		ll l = i.first, r = i.second;
		if (l > p) ans -= (l - p);
		p = max(p, r + 1);
	}
	ans -= (x - p);
	cout << ans;
	return 0;
}
/*
		  _ _ _ _                  _ _ _ _                _ _ _ _
		/      / \                /     / |              /     / |
	       /``````\   \              |`````|  |             |`````|  |
	      /        \   \             |     |  |             |     |  |
	     /          \   \            |     |  |             |     |  |
	    /     /\     \   \           |     |  |             |     |  |
	   /     / /\     \   \          |     |  |             |     |  |
	  /     / /  \     \   \         |     |  |             |     |  |
	 /     / /_ _ \     \   \        |     |  |             |     |  |
	/     /_ _ _ _ \     \   \       |     |  |             |     |  |
       /                      \   \      |     |  |_ _ _ _      |     |  |
      /      _ _ _ _ _ _ _     \   \     |     | /        /|    |     |  |
     /     / /            \     \   \    |     |/_ _ _ _ / |    |     |  |
    /     / /              \     \  /    |               | /    |     | /
   /_ _ _/_/                \_ _ _\/     |_ _ _ _ _ _ _ _|/     |_ _ _|/
*/

• 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