oj.uz

Submission #125094

# Submission time Handle Problem Language Result Execution time Memory
125094 2019-07-04T15:15:50 Z Just_Solve_The_Problem Strange Device (APIO19_strange_device) C++11
35 / 100
 631 ms 17064 KB 
#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define Ok puts("ok");

using namespace std;

const int N = (int)1e6 + 7;

ll a, b, gc;
int n;
ll maxn;
int used[N * 2];

ll gcd(ll a, ll b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

main() {
	scanf("%d %lld %lld", &n, &a, &b);
	bool ok = 0;
	if (log10(a / gcd(b + 1, a)) + log10(b) > 18) {
		ok = 1;
	}
	maxn = a / gcd(b + 1, a) * b;
	ll ans = 0;
	ll l, r;
	vector<pair<ll, ll>> vec;
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &l, &r);	
		if (ok) {
			ans += (r - l + 1);
		}
		if (r - l + 1 >= maxn) {
			cout << maxn;
			return 0;
		}
		if (l % maxn > r % maxn) {
			vec.push_back({l % maxn, maxn - 1});
			vec.push_back({0, r % maxn});
		} else {
			vec.push_back({l % maxn, r % maxn});
		}
		//cout << tr.get(0, maxn - 1) << endl;
		//cout << l % maxn << ' ' << r % maxn << endl;
	}
	if (ok) {
		cout << ans;
		return 0;
	}
	ans = 0;
	sort(vec.begin(), vec.end());
	ll cur = -1;
	for (int i = 0; i < vec.size(); i++) {
		 // cout << vec[i].fr << ' ' << vec[i].sc << ' ' << cur << ' ' << ans << endl;
		if (vec[i].sc < cur) continue;
		ans += (vec[i].sc - max(cur + 1, vec[i].fr) + 1);
		cur = max(cur, vec[i].sc);
	}
	cout << ans << endl;
	return 0;
	for (ll i = 1; i <= 50; i++) {
		cout << i << "| (" << (i + i / b) % a << ", " << i % b << ')' << endl;
	}
}
/*
3 3 3
4 4
7 9
17 18
*/

Compilation message

strange_device.cpp:25:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
strange_device.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %lld", &n, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &l, &r); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 736 KB Output is correct
3 Correct 8 ms 888 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 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 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 7 ms 760 KB Output is correct
17 Correct 62 ms 2540 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 576 ms 16924 KB Output is correct
3 Correct 544 ms 16924 KB Output is correct
4 Correct 538 ms 16864 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 576 ms 16924 KB Output is correct
3 Correct 544 ms 16924 KB Output is correct
4 Correct 538 ms 16864 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 551 ms 16848 KB Output is correct
7 Correct 554 ms 17064 KB Output is correct
8 Correct 547 ms 17056 KB Output is correct
9 Correct 605 ms 16884 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 576 ms 16924 KB Output is correct
3 Correct 544 ms 16924 KB Output is correct
4 Correct 538 ms 16864 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 54 ms 2536 KB Output is correct
7 Correct 59 ms 2488 KB Output is correct
8 Correct 56 ms 2472 KB Output is correct
9 Correct 56 ms 2540 KB Output is correct
10 Correct 54 ms 2516 KB Output is correct
11 Correct 58 ms 2460 KB Output is correct
12 Correct 54 ms 2512 KB Output is correct
13 Correct 60 ms 2512 KB Output is correct
14 Correct 54 ms 2540 KB Output is correct
15 Correct 62 ms 2540 KB Output is correct
16 Correct 60 ms 2536 KB Output is correct
17 Correct 58 ms 2512 KB Output is correct
18 Correct 555 ms 16944 KB Output is correct
19 Correct 534 ms 16900 KB Output is correct
20 Correct 605 ms 16828 KB Output is correct
21 Correct 60 ms 2668 KB Output is correct
22 Correct 52 ms 2628 KB Output is correct
23 Correct 204 ms 8668 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 59 ms 2536 KB Output is correct
3 Correct 60 ms 2536 KB Output is correct
4 Correct 631 ms 16856 KB Output is correct
5 Correct 58 ms 2536 KB Output is correct
6 Correct 59 ms 2508 KB Output is correct
7 Correct 59 ms 2352 KB Output is correct
8 Correct 61 ms 2572 KB Output is correct
9 Correct 59 ms 2532 KB Output is correct
10 Correct 60 ms 2540 KB Output is correct
11 Correct 60 ms 2508 KB Output is correct
12 Correct 53 ms 2540 KB Output is correct
13 Correct 60 ms 2540 KB Output is correct
14 Correct 625 ms 16836 KB Output is correct
15 Correct 59 ms 2540 KB Output is correct
16 Correct 539 ms 16808 KB Output is correct
17 Correct 542 ms 16848 KB Output is correct
18 Incorrect 1 ms 324 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 736 KB Output is correct
3 Correct 8 ms 888 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 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 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 7 ms 760 KB Output is correct
17 Correct 62 ms 2540 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct