Submission #156928

#	Time	Username	Problem	Language	Result	Execution time	Memory
156928		popovicirobert	Strange Device (APIO19_strange_device)	C++14	100 / 100	770 ms	53456 KiB

strange_device

#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(a / g <= INF / b) {
		per = (a / g);
		per *= b;
	}
	

	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: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30