oj.uz

Submission #519315

# Submission time Handle Problem Language Result Execution time Memory
519315 2022-01-26T07:50:26 Z tibinyte Strange Device (APIO19_strange_device) C++14
0 / 100
 30 ms 332 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 + 1;
	}
	else {
		p = a / gcd(a, b + 1) * b;
	}
	map<int, int> wh;
	auto update = [&](int st, int dr) {
		wh[st]++;
		wh[dr + 1]--;
	};
	for (int i = 1; i <= n; ++i) {
		int st, dr;
		cin >> st >> dr;
		int 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<int, int>::iterator i = wh.begin(); i != prev(wh.end()); ++i) {
		s += i->second;
		int st = i->first, dr = next(i)->first - 1;
		if (s) {
			ans += dr - st + 1;
		}
	}
	cout << ans;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 30 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 30 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 30 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 3 ms 324 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 300 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -