Submission #447188

#	Time	Username	Problem	Language	Result	Execution time	Memory
447188		Ya_Ali	Strange Device (APIO19_strange_device)	C++17	10 / 100	531 ms	16988 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;
// #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), S = 0;
	// cout << x << endl;
	x = 1ll * x * B;
	// cout << x << endl;
	vector<pair<ll, ll>> b;
	while (n--) {
		ll l, r;
		cin >> l >> r;
		l--, r--;
		if (r - l + 1 >= x) return cout << x, 0;
		S = S + (r - l + 1);
		l %= x, r %= x;
		if (r >= l) b.push_back({l, r});
		else b.push_back({l, x - 1}), b.push_back({0, r});
	}
	if (x > 1e18) return cout << S, 0;
	sort(b.begin(), b.end());
	ll p = 0, ans = x;
	// cout << x  << endl;
	for (auto i : b) {
		ll l = i.first, r = i.second;
		// cout << l << ' ' << r << endl;
		if (l > p) ans -= (l - p);
		p = r + 1;
	}
	ans -= (x - p);
	cout << ans;

	return 0;
}
/*
		  _ _ _ _                  _ _ _ _                _ _ _ _
		/      / \                /     / |              /     / |
	       /``````\   \              |`````|  |             |`````|  |
	      /        \   \             |     |  |             |     |  |
	     /          \   \            |     |  |             |     |  |
	    /     /\     \   \           |     |  |             |     |  |
	   /     / /\     \   \          |     |  |             |     |  |
	  /     / /  \     \   \         |     |  |             |     |  |
	 /     / /_ _ \     \   \        |     |  |             |     |  |
	/     /_ _ _ _ \     \   \       |     |  |             |     |  |
       /                      \   \      |     |  |_ _ _ _      |     |  |
      /      _ _ _ _ _ _ _     \   \     |     | /        /|    |     |  |
     /     / /            \     \   \    |     |/_ _ _ _ / |    |     |  |
    /     / /              \     \  /    |               | /    |     | /
   /_ _ _/_/                \_ _ _\/     |_ _ _ _ _ _ _ _|/     |_ _ _|/
*/

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