Submission #677092

#	Time	Username	Problem	Language	Result	Execution time	Memory
677092		amir	Strange Device (APIO19_strange_device)	C++17	100 / 100	472 ms	69776 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)x.size() 
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
const ll maxn = 1e6 + 6 , MX = 1e18+3 ;
ll A , B , S ;
ll n ;
ll l[maxn] , r[maxn] ;
vector<pair<ll , ll > > v ;


ll Gcd(ll a , ll b){
	if (b > a) swap(a , b) ;
	if (b == 0){
		return a ;
	}
	return Gcd(b , (a%b)) ;
}

void calS(){
	ll G = Gcd(A , B+1) ;
	ll X = (A / G) ;
	if (X > (MX/B)){
		S = MX ;
	}
	else {
		S = (X*B) ;
	}
}


int main()
{
    ios::sync_with_stdio(false) ; 
	cin.tie(NULL) ;
	cout.tie(NULL) ;
	cin >> n >> A >> B ;
	calS() ;
	for (int i = 0 ;i < n;  i++){
		cin >> l[i] >> r[i]  ;
	}
	ll ans = 0 ;
	for (int i = 0 ;i < n ;i++){
		ll len = r[i]-l[i]+1 ;
		if (len >= S){
			cout << S << '\n' ;
			return 0 ;
		}
		ll x = (l[i] % S) ;
		ll y = (r[i] % S) ;
		if (x <= y){
			v.ps(mp(x , y)) ;
		}
		else {
			v.ps(mp(x , S-1)) ;
			v.ps(mp(0 , y)) ;
		}
	}
	sort(all(v)) ;
	for (int i = 0 ;i < sz(v) ; i++){
		int j = i ; 
		pair<ll , ll > a = v[j] ;
		bool flag = true ;
		while(flag && j < sz(v)){
			if (v[j].first <= a.second+1){
				a.second = max(v[j].second , a.second) ;
				j ++ ;
			}
			else{
				flag = false ;
			}
		}
		i = j-1 ;
		ans += (a.second-a.first+1) ;
	}
	cout << ans << '\n' ;
}

• 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