oj.uz

Submission #977081

# Submission time Handle Problem Language Result Execution time Memory
977081 2024-05-07T11:15:22 Z dubabuba Strange Device (APIO19_strange_device) C++14
10 / 100
 1191 ms 63164 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) {
		if(r < p.ff) {
			ans += (r - l + 1);
			l = p.ff;
			r = p.ss;
		}
		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 0 ms 348 KB Output is correct
2 Incorrect 11 ms 952 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 1 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 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 685 ms 404 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1153 ms 63164 KB Output is correct
3 Correct 1137 ms 63012 KB Output is correct
4 Correct 1191 ms 62916 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1153 ms 63164 KB Output is correct
3 Correct 1137 ms 63012 KB Output is correct
4 Correct 1191 ms 62916 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1127 ms 62920 KB Output is correct
7 Correct 1104 ms 63140 KB Output is correct
8 Correct 1154 ms 63032 KB Output is correct
9 Incorrect 1142 ms 62960 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 348 KB Output is correct
2 Correct 1153 ms 63164 KB Output is correct
3 Correct 1137 ms 63012 KB Output is correct
4 Correct 1191 ms 62916 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 107 ms 6468 KB Output is correct
7 Correct 109 ms 6428 KB Output is correct
8 Correct 109 ms 6536 KB Output is correct
9 Correct 126 ms 6580 KB Output is correct
10 Correct 108 ms 6568 KB Output is correct
11 Correct 108 ms 6484 KB Output is correct
12 Correct 108 ms 6480 KB Output is correct
13 Incorrect 119 ms 6644 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 344 KB Output is correct
2 Incorrect 115 ms 6484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 11 ms 952 KB Output isn't correct
3 Halted 0 ms 0 KB -