oj.uz

Submission #393914

# Submission time Handle Problem Language Result Execution time Memory
393914 2021-04-24T21:34:18 Z ritul_kr_singh Strange Device (APIO19_strange_device) C++17
15 / 100
 627 ms 16932 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 last = -1, res = 0;
	sort(q.begin(), q.end(), comp);

	for(auto &i : q){
		res += i[1] - max(last, i[0] - 1LL);
		last = i[1];
	}

	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 5 ms 716 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 1 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 0 ms 204 KB Output is correct
2 Correct 530 ms 16828 KB Output is correct
3 Correct 524 ms 16768 KB Output is correct
4 Correct 512 ms 16864 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 530 ms 16828 KB Output is correct
3 Correct 524 ms 16768 KB Output is correct
4 Correct 512 ms 16864 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 524 ms 16932 KB Output is correct
7 Correct 528 ms 16892 KB Output is correct
8 Correct 522 ms 16796 KB Output is correct
9 Correct 598 ms 16908 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 530 ms 16828 KB Output is correct
3 Correct 524 ms 16768 KB Output is correct
4 Correct 512 ms 16864 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 60 ms 2472 KB Output is correct
7 Correct 53 ms 2456 KB Output is correct
8 Correct 51 ms 2516 KB Output is correct
9 Correct 50 ms 2400 KB Output is correct
10 Correct 49 ms 2440 KB Output is correct
11 Correct 63 ms 2496 KB Output is correct
12 Correct 58 ms 2480 KB Output is correct
13 Correct 54 ms 2496 KB Output is correct
14 Correct 48 ms 2388 KB Output is correct
15 Incorrect 56 ms 2444 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 64 ms 2440 KB Output is correct
3 Correct 56 ms 2540 KB Output is correct
4 Correct 627 ms 16804 KB Output is correct
5 Correct 54 ms 2504 KB Output is correct
6 Correct 58 ms 2464 KB Output is correct
7 Correct 56 ms 2412 KB Output is correct
8 Correct 57 ms 2492 KB Output is correct
9 Correct 76 ms 2504 KB Output is correct
10 Correct 54 ms 2388 KB Output is correct
11 Correct 55 ms 2412 KB Output is correct
12 Correct 45 ms 2480 KB Output is correct
13 Correct 57 ms 2428 KB Output is correct
14 Incorrect 596 ms 16784 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 5 ms 716 KB Output isn't correct
3 Halted 0 ms 0 KB -