Submission #316827

#TimeUsernameProblemLanguageResultExecution timeMemory
316827sofapudenStrange Device (APIO19_strange_device)C++14
10 / 100
3224 ms25344 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
	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/(a*b))-(l/(a*b)) >= 2 || ((r/(a*b))-(l/(a*b)) >= 1 && (r%(a*b)) >= (l%(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());
	pair<ll,ll> hi= {1ll,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.second+1){
			ans += inter[i][1] - hi.second -1;
		}
		hi = max(hi,make_pair(1ll,inter[i][2]));
	}
	if(inter[0][0] == 1){
		ans+=a*b-hi.second-1;
	}
	else{
		ans+=max(0ll,inter[0][1]-hi.second-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...