oj.uz

Submission #977074

# Submission time Handle Problem Language Result Execution time Memory
977074 2024-05-07T11:09:08 Z dubabuba Strange Device (APIO19_strange_device) C++14
10 / 100
 1172 ms 63020 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
 
int gcd(int a, int b) {
	if(a == 0) return b;
	if(b == 0) return a;
	return gcd(b % a, a);
}
 
signed main() {
	int a, b, n, t;
	cin >> n >> a >> b;
	int d = gcd(a, b + 1);

	double sda = 1.0  * a / d * b;
	if(sda <= 1e18) t = a / d * b;
	else t = 1e18;
	set<pii> v;
 
	int l, r; bool gay = false;
	for(int i = 0; i < n; i++) {
		cin >> l >> r;
		if(r - l + 1 >= t) {
			gay = 1;
			continue;
		}
 
		l %= t;
		r %= t;
 
		if(l <= r) {
			// root->upt(l, r);
			v.insert(MP(l, r));
		}
		else {
			// root->upt(l, t - 1);
			// root->upt(0, r);
			v.insert(MP(l, t - 1));
			v.insert(MP(0, r));
		}
	}
 
	if(gay) {
		cout << t << endl;
		if(t == (int) 1e18)
			return 1;
		return 0;
	}
 
	int ans = 0;
	l = 0, r = 0;
	for(pii p : v) {
		// cout << p.ff << ' ' << p.ss << endl;
		if(r < p.ff) {
			// cout << " + " << r - l + 1 << endl;
			ans += (r - l + 1);
			l = p.ff;
		}
		r = max(r, p.ss);
	}
 
	ans += (r - l + 1);
	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 11 ms 996 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 636 ms 408 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1076 ms 62896 KB Output is correct
3 Correct 1071 ms 62908 KB Output is correct
4 Correct 1116 ms 62988 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1076 ms 62896 KB Output is correct
3 Correct 1071 ms 62908 KB Output is correct
4 Correct 1116 ms 62988 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1083 ms 62904 KB Output is correct
7 Correct 1119 ms 62980 KB Output is correct
8 Correct 1098 ms 62988 KB Output is correct
9 Incorrect 1172 ms 63020 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1076 ms 62896 KB Output is correct
3 Correct 1071 ms 62908 KB Output is correct
4 Correct 1116 ms 62988 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 101 ms 6544 KB Output is correct
7 Correct 113 ms 6484 KB Output is correct
8 Correct 101 ms 6476 KB Output is correct
9 Correct 109 ms 6520 KB Output is correct
10 Correct 106 ms 6676 KB Output is correct
11 Correct 131 ms 6668 KB Output is correct
12 Correct 107 ms 6484 KB Output is correct
13 Incorrect 104 ms 6432 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 105 ms 6632 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 348 KB Output is correct
2 Incorrect 11 ms 996 KB Output isn't correct
3 Halted 0 ms 0 KB -