oj.uz

Submission #156926

# Submission time Handle Problem Language Result Execution time Memory
156926 2019-10-08T10:30:25 Z popovicirobert Strange Device (APIO19_strange_device) C++14
5 / 100
 849 ms 53412 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(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 464 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Incorrect 2 ms 376 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 376 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 376 KB Output is correct
5 Correct 469 ms 41428 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 645 ms 53204 KB Output is correct
3 Runtime error 2 ms 504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
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 645 ms 53204 KB Output is correct
3 Runtime error 2 ms 504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
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 645 ms 53204 KB Output is correct
3 Runtime error 2 ms 504 KB Execution killed with signal 8 (could be triggered by violating memory limits)
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 5736 KB Output is correct
3 Correct 71 ms 5740 KB Output is correct
4 Correct 849 ms 53412 KB Output is correct
5 Correct 72 ms 5736 KB Output is correct
6 Correct 70 ms 5748 KB Output is correct
7 Correct 71 ms 5724 KB Output is correct
8 Correct 73 ms 5812 KB Output is correct
9 Correct 69 ms 5764 KB Output is correct
10 Correct 70 ms 5784 KB Output is correct
11 Correct 70 ms 5756 KB Output is correct
12 Correct 62 ms 5732 KB Output is correct
13 Correct 70 ms 5608 KB Output is correct
14 Correct 729 ms 53368 KB Output is correct
15 Incorrect 69 ms 5736 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 464 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -