oj.uz

Submission #156927

# Submission time Handle Problem Language Result Execution time Memory
156927 2019-10-08T10:33:13 Z popovicirobert Strange Device (APIO19_strange_device) C++14
10 / 100
 741 ms 17064 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 
    
using namespace std;

const ll INF = 1e18 + 5;

inline ll gcd(ll a, ll b) {
	while(b > 0) {
		ll r = a % b;
		a = b;
		b = r;
	}
	return a;
}
   
int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int n, i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	ll a, b;
	cin >> n >> a >> b;
	ll g = gcd(a, b + 1), per = INF;
	if(b / g <= INF / a) {
		per = (b / g);
		per *= a;
	}
	

	vector < pair <ll, ll> > segm;
	for(i = 0; i < n; i++) {
		ll l, r;
		cin >> l >> r;
		if(r - l + 1 >= per) {
			cout << per;
			return 0;
		}
		if(l == r) {
			l %= per, r %= per;
			segm.push_back({l, r});
		}
		else {
			l %= per, r %= per;
			if(l >= r) {
				segm.push_back({l, per - 1});
				segm.push_back({0, r});
			}
			else {
				segm.push_back({l, r});
			}
		}
	}
	sort(segm.begin(), segm.end(), [&](const pair <ll, ll> &x, const pair <ll, ll> &y) {
				if(x.first == y.first) return x.second > y.second;
				return x.first < y.first;
		});

	ll last = -1, ans = 0;
	for(auto &it : segm) {
		if(last < it.first) {
			ans += it.second - it.first + 1;
			last = it.second;
		}
		else if(it.second >= last) {
			ans += it.second - last;
			last = it.second;
		}
	}
	cout << ans;
		
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 8 ms 1092 KB Output is correct
3 Correct 8 ms 1144 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 388 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is 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 376 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 462 ms 16980 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 70 ms 2924 KB Output is correct
3 Correct 70 ms 3052 KB Output is correct
4 Correct 741 ms 16956 KB Output is correct
5 Correct 70 ms 2932 KB Output is correct
6 Correct 70 ms 2928 KB Output is correct
7 Correct 71 ms 2952 KB Output is correct
8 Correct 84 ms 2924 KB Output is correct
9 Correct 68 ms 2924 KB Output is correct
10 Correct 69 ms 3016 KB Output is correct
11 Correct 70 ms 2924 KB Output is correct
12 Correct 65 ms 2952 KB Output is correct
13 Correct 70 ms 2928 KB Output is correct
14 Correct 724 ms 17064 KB Output is correct
15 Incorrect 70 ms 2928 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 8 ms 1092 KB Output is correct
3 Correct 8 ms 1144 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -