oj.uz

답안 #564143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564143 2022-05-18T15:32:56 Z ngpin04 이상한 기계 (APIO19_strange_device) C++14
15 / 100
 598 ms 33468 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);
	assert(len < 2 * ooo);

	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;
		// cerr << pre << " " << pir.fi << "\n";
		cnt += pir.se;
		pre = pir.fi;
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 4 ms 856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 321 ms 33220 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 475 ms 33244 KB Output is correct
3 Correct 496 ms 33212 KB Output is correct
4 Correct 459 ms 33248 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 475 ms 33244 KB Output is correct
3 Correct 496 ms 33212 KB Output is correct
4 Correct 459 ms 33248 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 480 ms 33164 KB Output is correct
7 Correct 457 ms 33232 KB Output is correct
8 Correct 464 ms 33200 KB Output is correct
9 Correct 550 ms 33208 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 475 ms 33244 KB Output is correct
3 Correct 496 ms 33212 KB Output is correct
4 Correct 459 ms 33248 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 47 ms 4556 KB Output is correct
7 Correct 48 ms 4548 KB Output is correct
8 Correct 48 ms 4552 KB Output is correct
9 Correct 47 ms 4456 KB Output is correct
10 Correct 44 ms 4544 KB Output is correct
11 Incorrect 46 ms 4480 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 50 ms 4540 KB Output is correct
3 Correct 57 ms 4548 KB Output is correct
4 Correct 598 ms 33232 KB Output is correct
5 Correct 50 ms 4556 KB Output is correct
6 Correct 54 ms 4468 KB Output is correct
7 Correct 50 ms 4512 KB Output is correct
8 Correct 55 ms 4580 KB Output is correct
9 Correct 48 ms 4556 KB Output is correct
10 Correct 54 ms 4556 KB Output is correct
11 Correct 51 ms 4476 KB Output is correct
12 Correct 44 ms 4548 KB Output is correct
13 Correct 55 ms 4512 KB Output is correct
14 Correct 558 ms 33468 KB Output is correct
15 Correct 56 ms 4588 KB Output is correct
16 Correct 447 ms 33284 KB Output is correct
17 Correct 472 ms 33268 KB Output is correct
18 Runtime error 1 ms 468 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 4 ms 856 KB Output isn't correct
3 Halted 0 ms 0 KB -