oj.uz

Submission #564110

# Submission time Handle Problem Language Result Execution time Memory
564110 2022-05-18T15:10:36 Z ngpin04 Strange Device (APIO19_strange_device) C++14
40 / 100
 617 ms 68932 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

long long lcm(long long a, long long b) {
	long long res = a / __gcd(a, b);
	if (res > 2 * ooo / b)
		return 2 * ooo;
	return res * b;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	long long n, A, B;
	cin >> n >> A >> B;
	long long x = __gcd(A, B + 1);
	long long y = __gcd(A, B);
	A /= x;
	if (A > 2 * ooo / y)
		A = 2 * ooo;	
	else
		A *= y;

	long long len = lcm(A, B);

	vector <pair <long long, int>> events;

	for (int i = 1; i <= n; i++) {
		long long l, r;
		cin >> l >> r;
		if (r - l + 1 >= len)
			return cout << len, 0;
		events.push_back(mp(l % len, 1));
		events.push_back(mp(r % len + 1, -1));
		if (l % len > r % len) {
			events.push_back(mp(0, 1));
			events.push_back(mp(len, -1));
		}	
			
	}
	sort(ALL(events));

	long long ans = 0;
	long long pre = 0;
	int cnt = 0;
	for (pair <long long, int> pir : events) {
		if (cnt > 0) 
			ans += pir.fi - pre;
		cnt += pir.se;
		pre = pir.fi;
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 6 ms 1236 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 330 ms 37532 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 505 ms 44616 KB Output is correct
3 Correct 514 ms 48312 KB Output is correct
4 Correct 477 ms 33820 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 505 ms 44616 KB Output is correct
3 Correct 514 ms 48312 KB Output is correct
4 Correct 477 ms 33820 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 497 ms 33904 KB Output is correct
7 Correct 521 ms 66900 KB Output is correct
8 Correct 538 ms 67000 KB Output is correct
9 Correct 590 ms 68932 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 505 ms 44616 KB Output is correct
3 Correct 514 ms 48312 KB Output is correct
4 Correct 477 ms 33820 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 51 ms 7248 KB Output is correct
7 Correct 53 ms 7392 KB Output is correct
8 Correct 50 ms 7280 KB Output is correct
9 Correct 49 ms 7224 KB Output is correct
10 Correct 50 ms 7232 KB Output is correct
11 Incorrect 48 ms 7232 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 53 ms 7280 KB Output is correct
3 Correct 55 ms 7244 KB Output is correct
4 Correct 617 ms 49208 KB Output is correct
5 Correct 56 ms 7256 KB Output is correct
6 Correct 54 ms 7336 KB Output is correct
7 Correct 52 ms 7252 KB Output is correct
8 Correct 59 ms 7256 KB Output is correct
9 Correct 53 ms 7224 KB Output is correct
10 Correct 60 ms 7240 KB Output is correct
11 Correct 53 ms 7172 KB Output is correct
12 Correct 48 ms 7236 KB Output is correct
13 Correct 53 ms 7176 KB Output is correct
14 Correct 589 ms 38944 KB Output is correct
15 Correct 57 ms 7260 KB Output is correct
16 Correct 454 ms 40328 KB Output is correct
17 Correct 496 ms 38828 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 30.0

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