oj.uz

Submission #447185

# Submission time Handle Problem Language Result Execution time Memory
447185 2021-07-25T05:01:18 Z Ya_Ali Strange Device (APIO19_strange_device) C++17
10 / 100
 584 ms 53212 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;
#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);
	x = 1ll * x * B;
	vector<pair<ll, ll>> b;
	while (n--) {
		ll l, r;
		cin >> l >> r;
		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;
	// 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 0 ms 320 KB Output is correct
2 Incorrect 6 ms 976 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 Correct 1 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 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 1 ms 204 KB Output is correct
2 Correct 509 ms 53084 KB Output is correct
3 Correct 500 ms 53136 KB Output is correct
4 Correct 495 ms 53212 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 509 ms 53084 KB Output is correct
3 Correct 500 ms 53136 KB Output is correct
4 Correct 495 ms 53212 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 493 ms 53204 KB Output is correct
7 Correct 495 ms 53140 KB Output is correct
8 Correct 482 ms 53204 KB Output is correct
9 Correct 517 ms 53136 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 509 ms 53084 KB Output is correct
3 Correct 500 ms 53136 KB Output is correct
4 Correct 495 ms 53212 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 48 ms 5696 KB Output is correct
7 Correct 50 ms 5696 KB Output is correct
8 Correct 49 ms 5636 KB Output is correct
9 Correct 49 ms 5612 KB Output is correct
10 Correct 48 ms 5684 KB Output is correct
11 Correct 49 ms 5688 KB Output is correct
12 Correct 50 ms 5692 KB Output is correct
13 Correct 50 ms 5720 KB Output is correct
14 Correct 48 ms 5692 KB Output is correct
15 Incorrect 54 ms 5712 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 5692 KB Output is correct
3 Correct 51 ms 5696 KB Output is correct
4 Correct 584 ms 53204 KB Output is correct
5 Correct 50 ms 5696 KB Output is correct
6 Correct 54 ms 5600 KB Output is correct
7 Correct 52 ms 5740 KB Output is correct
8 Correct 53 ms 5636 KB Output is correct
9 Correct 52 ms 5700 KB Output is correct
10 Correct 51 ms 5716 KB Output is correct
11 Correct 51 ms 5672 KB Output is correct
12 Correct 46 ms 5628 KB Output is correct
13 Correct 51 ms 5708 KB Output is correct
14 Incorrect 546 ms 53092 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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