oj.uz

Submission #171749

# Submission time Handle Problem Language Result Execution time Memory
171749 2019-12-30T09:18:27 Z Sensei Strange Device (APIO19_strange_device) C++17
65 / 100
 667 ms 53436 KB 
/*
	DATE:		2019-12-30 11:10:15
	NAME:		
	PROBLEM:	APIO19_strange_device
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;
const long long LLINF = 1e18 + 100;

class Segment {
public:
	long long l, r;
	Segment() {}
	Segment(long long x, long long y) {
		l = x;
		r = y;
	}
};

long long f(long long x, long long y) {
	if (x / __gcd(x, y + 1) > LLINF / y) {
		return LLINF;
	}

	return x * y / __gcd(x, y + 1);
}

int main() {
	int n;
	cin >> n;

	long long A, B;
	cin >> A >> B;

	long long C = f(A, B);

	vector<Segment> segments;

	for (int i = 1; i <= n; i++) {
		Segment segment;
		scanf("%lld %lld", &segment.l, &segment.r);

		segment.l %= C;
		segment.r %= C;

		if (segment.l <= segment.r) {
			segments.push_back(segment);
		}
		else {
			segments.push_back(Segment(0, segment.r));
			segments.push_back(Segment(segment.l, C - 1));
		}
	}

	sort(segments.begin(), segments.end(), [](Segment x, Segment y) {
		if (x.l == y.l) {
			return x.r < y.r;
		}

		return x.l < y.l;
	});

	long long lastr = -1;
	long long ans = 0;

	for (int i = 0; i < segments.size(); i++) {
		if (segments[i].l > lastr) {
			lastr = segments[i].l - 1;
		}

		if (segments[i].r > lastr) {
			ans += segments[i].r - lastr;
			lastr = segments[i].r;
		}
	}

	cout << ans << "\n";

	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < segments.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
strange_device.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &segment.l, &segment.r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct
3 Correct 8 ms 1016 KB Output is correct
4 Correct 2 ms 360 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 7 ms 1016 KB Output is correct
17 Correct 62 ms 5732 KB Output is correct
18 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 446 ms 16884 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 540 ms 17048 KB Output is correct
3 Correct 550 ms 16976 KB Output is correct
4 Correct 556 ms 33648 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 540 ms 17048 KB Output is correct
3 Correct 550 ms 16976 KB Output is correct
4 Correct 556 ms 33648 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 555 ms 46816 KB Output is correct
7 Correct 545 ms 40892 KB Output is correct
8 Correct 555 ms 40724 KB Output is correct
9 Correct 643 ms 53276 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 540 ms 17048 KB Output is correct
3 Correct 550 ms 16976 KB Output is correct
4 Correct 556 ms 33648 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 53 ms 5732 KB Output is correct
7 Correct 59 ms 5732 KB Output is correct
8 Correct 55 ms 5732 KB Output is correct
9 Correct 59 ms 5816 KB Output is correct
10 Correct 53 ms 5732 KB Output is correct
11 Correct 59 ms 5880 KB Output is correct
12 Correct 56 ms 5764 KB Output is correct
13 Correct 63 ms 5696 KB Output is correct
14 Correct 53 ms 5732 KB Output is correct
15 Correct 62 ms 5732 KB Output is correct
16 Correct 61 ms 5732 KB Output is correct
17 Correct 59 ms 5756 KB Output is correct
18 Correct 569 ms 53288 KB Output is correct
19 Correct 554 ms 53276 KB Output is correct
20 Correct 667 ms 53436 KB Output is correct
21 Correct 60 ms 5732 KB Output is correct
22 Correct 54 ms 5732 KB Output is correct
23 Correct 204 ms 18532 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 59 ms 2792 KB Output is correct
3 Correct 60 ms 2764 KB Output is correct
4 Correct 639 ms 17468 KB Output is correct
5 Correct 60 ms 2792 KB Output is correct
6 Correct 61 ms 2792 KB Output is correct
7 Correct 61 ms 2796 KB Output is correct
8 Correct 63 ms 2892 KB Output is correct
9 Correct 59 ms 2792 KB Output is correct
10 Correct 59 ms 2792 KB Output is correct
11 Correct 60 ms 2792 KB Output is correct
12 Correct 53 ms 2732 KB Output is correct
13 Correct 60 ms 2796 KB Output is correct
14 Correct 623 ms 18360 KB Output is correct
15 Correct 59 ms 2800 KB Output is correct
16 Correct 556 ms 48564 KB Output is correct
17 Correct 550 ms 41420 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct
3 Correct 8 ms 1016 KB Output is correct
4 Correct 2 ms 360 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 7 ms 1016 KB Output is correct
17 Correct 62 ms 5732 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Incorrect 2 ms 256 KB Output isn't correct
21 Halted 0 ms 0 KB -