oj.uz

Submission #393915

# Submission time Handle Problem Language Result Execution time Memory
393915 2021-04-24T21:48:59 Z ritul_kr_singh Strange Device (APIO19_strange_device) C++17
15 / 100
 633 ms 17012 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e18;

bool comp(array<int, 2> &x, array<int, 2> &y){
	return x[1] < y[1];
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	int n, A, B, l, r; cin >> n >> A >> B;

	int g = A / __gcd(A, B + 1LL);

	if(g > INF / B) g = INF + 5;
	else g *= B;

	vector<array<int, 2>> q;
	bool all = false;

	while(n--){
		cin >> l >> r;
		int lm = l % g, rm = r % g;
		// if(l + (g - lm) <= r) q.push_back({lm, g-1}), q.push_back({0, rm});
		// else q.push_back({lm, rm});
		all = all or (r - l + 1LL >= g);
		if(lm <= rm) q.push_back({lm, rm});
		else q.push_back({lm, g-1LL}), q.push_back({0, rm});
	}

	int res = 0;
	l = -1, r = -2;
	sort(q.begin(), q.end(), comp);

	for(auto &i : q){
		if(r < i[0]){
			res += r - l + 1LL;
			l = i[0], r = i[1];
		}else r = i[1];
	}

	res += r - l + 1LL;

	if(all) res = g;

	cout << res;
}

Subtask #1
0 / 10.0

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

Subtask #2
5.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 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 553 ms 17012 KB Output is correct
3 Correct 518 ms 16904 KB Output is correct
4 Correct 520 ms 16804 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 553 ms 17012 KB Output is correct
3 Correct 518 ms 16904 KB Output is correct
4 Correct 520 ms 16804 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 521 ms 16812 KB Output is correct
7 Correct 534 ms 16800 KB Output is correct
8 Correct 521 ms 16852 KB Output is correct
9 Correct 606 ms 16828 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 553 ms 17012 KB Output is correct
3 Correct 518 ms 16904 KB Output is correct
4 Correct 520 ms 16804 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 49 ms 2384 KB Output is correct
7 Correct 54 ms 2488 KB Output is correct
8 Correct 51 ms 2504 KB Output is correct
9 Correct 51 ms 2536 KB Output is correct
10 Correct 49 ms 2412 KB Output is correct
11 Correct 52 ms 2404 KB Output is correct
12 Correct 50 ms 2496 KB Output is correct
13 Correct 56 ms 2496 KB Output is correct
14 Correct 48 ms 2504 KB Output is correct
15 Incorrect 57 ms 2440 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 55 ms 2400 KB Output is correct
3 Correct 55 ms 2464 KB Output is correct
4 Correct 633 ms 16868 KB Output is correct
5 Correct 55 ms 2496 KB Output is correct
6 Correct 55 ms 2428 KB Output is correct
7 Correct 61 ms 2408 KB Output is correct
8 Correct 57 ms 2504 KB Output is correct
9 Correct 54 ms 2568 KB Output is correct
10 Correct 54 ms 2440 KB Output is correct
11 Correct 55 ms 2500 KB Output is correct
12 Correct 46 ms 2412 KB Output is correct
13 Correct 62 ms 2496 KB Output is correct
14 Incorrect 614 ms 16788 KB Output isn't correct
15 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 6 ms 592 KB Output isn't correct
3 Halted 0 ms 0 KB -