Submission #1307611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307611		namhh	Strange Device (APIO19_strange_device)	C++20	65 / 100	329 ms	16980 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e3+5;
int n,a,b,l,r;
vector<pii>loj;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> a >> b;
	a /= __gcd(a,b+1);
	int cycle;
	if(a <= LLONG_MAX/b) cycle = a*b;
	else cycle = 4e18;
	for(int i = 1; i <= n; i++){
		cin >> l >> r;
		l %= cycle;
		r %= cycle;
		if(r-l+1 >= cycle){
			cout << cycle;
			return 0;
		}
		if(l <= r) loj.push_back({l,r});
		else{
			loj.push_back({l,cycle-1});
			loj.push_back({0,r});
		}
	}
	sort(loj.begin(),loj.end());
	l = loj[0].fi;
	r = loj[0].se;
	int ans = 0;
	for(int i = 1; i < loj.size(); i++){
		if(loj[i].fi > r){
			ans += r-l+1;
			l = loj[i].fi;
			r = loj[i].se;
		}
		else r = max(r,loj[i].se);
	}
	ans += r-l+1;
	cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 30