Submission #316832

#	Time	Username	Problem	Language	Result	Execution time	Memory
316832		sofapuden	Strange Device (APIO19_strange_device)	C++14	10 / 100	651 ms	25348 KiB

strange_device

#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(l%(a*b) > r%(a*b)){
			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 = -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";
}
	

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