제출 #316828

#제출 시각아이디문제언어결과실행 시간메모리
316828sofapudenStrange Device (APIO19_strange_device)C++14
10 / 100
639 ms25248 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, a, b; cin >> n >> a >> b;
	ll ans = 0;
	if(LONG_LONG_MAX/b <= a){
		for(int i = 0; i < n; ++i){
			ll l, r; cin >> l >> r;
			ans+=r-l+1ll;
		}
		cout << ans << "\n";
		return 0;	
	}
	vector<array<ll,3>> inter;
	for(int i = 0; i < n; ++i){
		ll l, r; cin >> l >> r;
		if(r-l+1 >= a*b){
			cout << a*b << "\n";
			return 0;
		}
		if((r/(a*b))-(l/(a*b)) >= 1){
			inter.push_back({0,l%(a*b),r%(a*b)});
		}
		else{
			inter.push_back({1,l%(a*b),r%(a*b)});
		}
	}
	sort(inter.begin(),inter.end());
	ll hi= inter[0][2];
	if(inter[0][0] == 1){
		ans = inter[0][1];
	}
	for(int i = 0; i < n; ++i){
		if(inter[i][0] && !inter[0][0] && inter[i][1] >= inter[0][1])break;
		if(inter[i][0] && inter[i][1] > hi+1){
			ans += inter[i][1] - hi -1;
		}
		hi = max(hi,inter[i][2]);
	}
	if(inter[0][0] == 1){
		ans+=a*b-hi-1;
	}
	else{
		ans+=max(0ll,inter[0][1]-hi-1);
	}
		
	cout << a*b - ans << "\n";
}
	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...