Submission #1257586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257586		MasterDebater	Strange Device (APIO19_strange_device)	C++20	100 / 100	352 ms	41336 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
const int N=1e6+10;
ll n,a,b,k,ans,li,ri,l[N],r[N];
vector<pii>v;
bool overflow(ll x,ll y){
	if(log10(x)+log10(y)>=log10(4e18))return 1;
	return 0;
}
bool cmp(pii a,pii b){
	if(a.F!=b.F)return a.F<b.F;
	return a.S>b.S;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>a>>b;
	for(int i=0;i<n;i++)cin>>l[i]>>r[i];
	if(overflow(a,(b+1)/(__gcd(a,b+1))))k=2e18;
	else k=a*(b+1)/__gcd(a,b+1),k/=(b+1),k*=b;
	//cout<<"k: "<<k<<'\n';
	if(k>=1e18){
		for(int i=0;i<n;i++)ans+=(r[i]-l[i]+1);
		cout<<ans;
		return 0;
	}
	for(int i=0;i<n;i++)if(r[i]-l[i]+1>=k){
		cout<<k;
		return 0;
	}
	for(int i=0;i<n;i++){
		l[i]%=k;
		r[i]%=k;
		if(r[i]<l[i])v.push_back({l[i],k-1}),v.push_back({0,r[i]});
		else v.push_back({l[i],r[i]});
	}
	li=-1,ri=-2;
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i<v.size();i++){
		if(v[i].F>ri)ans+=(ri-li+1),li=v[i].F,ri=v[i].S;
		else if(v[i].S>ri)ri=v[i].S;
	}
	ans+=(ri-li+1);
	cout<<ans;
	return 0;
}

• 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