oj.uz

답안 #519324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519324 2022-01-26T07:57:06 Z tibinyte 이상한 기계 (APIO19_strange_device) C++14
35 / 100
 754 ms 63080 KB 
#include <bits/stdc++.h>
using namespace std;
bool will_overflow(long long a, long long b) {
	long long c = a * b;
	if (a != c / b) {
		return true;
	}
	return false;
}
long long gcd(long long a, long long b) {
	while (b) {
		long long c = a % b;
		a = b;
		b = c;
	}
	return a;
}
int main() {
	cin.tie(nullptr)->ios_base::sync_with_stdio(false);
	long long n, a, b;
	cin >> n >> a >> b;
	long long p = 0;
	if (will_overflow(a / gcd(a, b + 1), b)) {
		p = 1e18;
	}
	else {
		p = a / gcd(a, b + 1) * b;
	}
	map<long long, long long> wh;
	auto update = [&](long long st, long long dr) {
		wh[st]++;
		wh[dr + 1]--;
	};
	wh[p - 1] = 0;
	wh[0] = 0;
	for (long long i = 1; i <= n; ++i) {
		long long st, dr;
		cin >> st >> dr;
		long long lg = (dr - st) + 1;
		st %= p;
		if (st + lg - 1 < p) {
			update(st, st + lg - 1);
		}
		else {
			update(st, p - 1);
			lg -= (p - st);
			st = 0;
			if (st + lg - 1 < p) {
				update(st, st + lg - 1);
			}
			else {
				cout << p << '\n';
				return 0;
			}
		}
	}
	long long ans = 0;
	long long s = 0;
	for (map<long long, long long>::iterator i = wh.begin(); i != prev(wh.end()); ++i) {
		s += i->second;
		long long st = i->first, dr = next(i)->first - 1;
		if (s) {
			ans += dr - st + 1;
		}
	}
	cout << ans;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 6 ms 844 KB Output is correct
3 Correct 6 ms 844 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 840 KB Output is correct
17 Correct 58 ms 6580 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 231 ms 288 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 650 ms 63076 KB Output is correct
3 Correct 672 ms 63072 KB Output is correct
4 Correct 723 ms 62916 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 650 ms 63076 KB Output is correct
3 Correct 672 ms 63072 KB Output is correct
4 Correct 723 ms 62916 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 657 ms 62904 KB Output is correct
7 Correct 669 ms 62876 KB Output is correct
8 Correct 668 ms 62812 KB Output is correct
9 Correct 754 ms 62896 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 650 ms 63076 KB Output is correct
3 Correct 672 ms 63072 KB Output is correct
4 Correct 723 ms 62916 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 54 ms 6636 KB Output is correct
7 Correct 70 ms 6524 KB Output is correct
8 Correct 65 ms 6480 KB Output is correct
9 Correct 72 ms 6532 KB Output is correct
10 Correct 57 ms 6476 KB Output is correct
11 Correct 55 ms 6536 KB Output is correct
12 Correct 64 ms 6468 KB Output is correct
13 Correct 69 ms 6476 KB Output is correct
14 Correct 57 ms 6564 KB Output is correct
15 Correct 68 ms 6604 KB Output is correct
16 Correct 65 ms 6496 KB Output is correct
17 Correct 65 ms 6448 KB Output is correct
18 Correct 637 ms 62828 KB Output is correct
19 Correct 677 ms 62904 KB Output is correct
20 Correct 708 ms 62848 KB Output is correct
21 Correct 60 ms 6528 KB Output is correct
22 Correct 64 ms 6536 KB Output is correct
23 Correct 103 ms 204 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 60 ms 6512 KB Output is correct
3 Correct 62 ms 6540 KB Output is correct
4 Correct 734 ms 62940 KB Output is correct
5 Correct 64 ms 6568 KB Output is correct
6 Correct 65 ms 6484 KB Output is correct
7 Correct 66 ms 6516 KB Output is correct
8 Correct 65 ms 6576 KB Output is correct
9 Correct 63 ms 6548 KB Output is correct
10 Correct 69 ms 6548 KB Output is correct
11 Correct 71 ms 6468 KB Output is correct
12 Correct 59 ms 6472 KB Output is correct
13 Correct 66 ms 6508 KB Output is correct
14 Correct 751 ms 62920 KB Output is correct
15 Correct 53 ms 6524 KB Output is correct
16 Correct 603 ms 62872 KB Output is correct
17 Correct 627 ms 63080 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 6 ms 844 KB Output is correct
3 Correct 6 ms 844 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 840 KB Output is correct
17 Correct 58 ms 6580 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct
19 Halted 0 ms 0 KB -