oj.uz

Submission #445798

# Submission time Handle Problem Language Result Execution time Memory
445798 2021-07-19T15:30:05 Z nonsensenonsense1 Strange Device (APIO19_strange_device) C++17
35 / 100
 582 ms 41168 KB 
#include <cstdio>
#include <vector>
#include <algorithm>

long long gcd(long long a, long long b) 
{
	while (a && b) {
		if (a > b) a %= b;
		else b %= a;
	}
	return a + b;
}

int n;
long long a, b, l, r;

int main() 
{
	scanf("%d%lld%lld", &n, &a, &b);
	long long d = b % a + 1, k = a / gcd(a, d), p;
	if (~((long long)1 << 63) >> 1 / k < b) p = ~((long long)1 << 63);
	else p = k * b;
	std::vector<std::pair<long long, long long> > s;
	for (int i = 0; i < n; ++i) {
		scanf("%lld%lld", &l, &r);
		if (r - l + 1 >= p) {
			printf("%lld\n", p);
			return 0;
		}
		l %= p;
		r %= p;
		if (l <= r) s.push_back(std::make_pair(l, r));
		else {
			s.push_back(std::make_pair(0, r));
			s.push_back(std::make_pair(l, p - 1));
		}
	}
	std::sort(s.begin(), s.end());
	long long ans = 0, l = 0, r = -1;
	for (int i = 0; i < (int)s.size(); ++i) {
		if (s[i].first <= r) {
			ans += std::max((long long)0, s[i].second - r);
			r = std::max(r, s[i].second);
		}
		else {
			ans += s[i].second - s[i].first + 1;
			l = s[i].first;
			r = s[i].second;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:39:21: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   39 |  long long ans = 0, l = 0, r = -1;
      |                     ^
strange_device.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf("%d%lld%lld", &n, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld%lld", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 8 ms 972 KB Output is correct
3 Correct 8 ms 1032 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 276 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 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 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 6 ms 972 KB Output is correct
17 Correct 58 ms 5632 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory 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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 367 ms 41168 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 528 ms 36168 KB Output is correct
3 Correct 511 ms 36180 KB Output is correct
4 Correct 519 ms 29096 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 528 ms 36168 KB Output is correct
3 Correct 511 ms 36180 KB Output is correct
4 Correct 519 ms 29096 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 500 ms 29920 KB Output is correct
7 Correct 542 ms 30012 KB Output is correct
8 Correct 519 ms 29912 KB Output is correct
9 Correct 559 ms 29952 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 528 ms 36168 KB Output is correct
3 Correct 511 ms 36180 KB Output is correct
4 Correct 519 ms 29096 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 51 ms 5648 KB Output is correct
7 Correct 54 ms 5600 KB Output is correct
8 Correct 50 ms 5660 KB Output is correct
9 Correct 55 ms 5640 KB Output is correct
10 Correct 50 ms 5556 KB Output is correct
11 Correct 57 ms 5640 KB Output is correct
12 Correct 50 ms 5576 KB Output is correct
13 Correct 55 ms 5556 KB Output is correct
14 Correct 53 ms 5660 KB Output is correct
15 Correct 56 ms 5660 KB Output is correct
16 Correct 55 ms 5660 KB Output is correct
17 Correct 51 ms 5672 KB Output is correct
18 Correct 519 ms 29884 KB Output is correct
19 Correct 497 ms 29872 KB Output is correct
20 Correct 546 ms 29908 KB Output is correct
21 Correct 53 ms 5552 KB Output is correct
22 Correct 48 ms 5612 KB Output is correct
23 Correct 157 ms 18480 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 54 ms 5632 KB Output is correct
3 Correct 53 ms 5564 KB Output is correct
4 Correct 582 ms 36132 KB Output is correct
5 Correct 53 ms 5552 KB Output is correct
6 Correct 53 ms 5596 KB Output is correct
7 Correct 52 ms 5612 KB Output is correct
8 Correct 54 ms 5616 KB Output is correct
9 Correct 57 ms 5648 KB Output is correct
10 Correct 55 ms 5756 KB Output is correct
11 Correct 54 ms 5584 KB Output is correct
12 Correct 48 ms 5580 KB Output is correct
13 Correct 55 ms 5556 KB Output is correct
14 Correct 561 ms 36116 KB Output is correct
15 Correct 55 ms 5612 KB Output is correct
16 Correct 507 ms 29956 KB Output is correct
17 Correct 508 ms 30044 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 8 ms 972 KB Output is correct
3 Correct 8 ms 1032 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 276 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 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 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 6 ms 972 KB Output is correct
17 Correct 58 ms 5632 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct