oj.uz

Submission #977084

# Submission time Handle Problem Language Result Execution time Memory
977084 2024-05-07T11:18:24 Z dubabuba Strange Device (APIO19_strange_device) C++14
10 / 100
 1177 ms 63192 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;
	}

	v.insert(MP(2e18, 2e18));
 
	int ans = 0;
	l = 0, r = 0;
	for(pii p : v) {
		if(r < p.ff) {
			ans += (r - l + 1);
			l = p.ff;
			r = p.ss;
		}
		r = max(r, p.ss);
	}

	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 860 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 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 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 1 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 690 ms 404 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1141 ms 62984 KB Output is correct
3 Correct 1177 ms 62892 KB Output is correct
4 Correct 1116 ms 63132 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1141 ms 62984 KB Output is correct
3 Correct 1177 ms 62892 KB Output is correct
4 Correct 1116 ms 63132 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1104 ms 63192 KB Output is correct
7 Correct 1123 ms 63084 KB Output is correct
8 Correct 1115 ms 63128 KB Output is correct
9 Incorrect 1142 ms 62876 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1141 ms 62984 KB Output is correct
3 Correct 1177 ms 62892 KB Output is correct
4 Correct 1116 ms 63132 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 106 ms 6524 KB Output is correct
7 Correct 107 ms 6612 KB Output is correct
8 Correct 124 ms 6472 KB Output is correct
9 Correct 108 ms 6480 KB Output is correct
10 Correct 106 ms 6476 KB Output is correct
11 Correct 110 ms 6484 KB Output is correct
12 Correct 113 ms 6812 KB Output is correct
13 Incorrect 108 ms 6564 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 109 ms 6496 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 860 KB Output isn't correct
3 Halted 0 ms 0 KB -