Submission #316826

#	Time	Username	Problem	Language	Result	Execution time	Memory
316826		sofapuden	Strange Device (APIO19_strange_device)	C++14	10 / 100	3214 ms	28884 KiB

strange_device

#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[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";
}
	

• 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