oj.uz

Submission #447189

# Submission time Handle Problem Language Result Execution time Memory
447189 2021-07-25T05:13:29 Z Ya_Ali Strange Device (APIO19_strange_device) C++17
5 / 100
 507 ms 16844 KB 
/* ** *** In the name of God *** ** */
// Only Haider is Amir al-Momenin
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 10;
// #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;
	if (x < inf / B) x = 1ll * x * B;
	else x = inf;
	// 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 7 ms 592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 492 ms 16832 KB Output is correct
3 Correct 484 ms 16840 KB Output is correct
4 Correct 506 ms 16792 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 492 ms 16832 KB Output is correct
3 Correct 484 ms 16840 KB Output is correct
4 Correct 506 ms 16792 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Incorrect 507 ms 16844 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 492 ms 16832 KB Output is correct
3 Correct 484 ms 16840 KB Output is correct
4 Correct 506 ms 16792 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Incorrect 50 ms 2448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 50 ms 2464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 7 ms 592 KB Output isn't correct
3 Halted 0 ms 0 KB -