Submission #1048992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048992		ihceker	Strange Device (APIO19_strange_device)	C++14	100 / 100	967 ms	70336 KiB

strange_device

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
using namespace std;

const int inf=1e18+5;
 
int32_t main(){
	int n,a,b;
	cin>>n>>a>>b;
	int x;
	if(inf/b<a/__gcd(a,b+1)){
		x=inf;
	}
	else x=b*(a/__gcd(a,b+1));
	vector<pair<int,int>>pre;
	for(int i=0;i<n;i++){
		int l,r;
		cin>>l>>r;
		if(r-l+1>=x){
			cout<<x<<endl;
			return 0;
		}
		if(l%x>r%x){
			pre.pb({0,1});
			pre.pb({r%x+1,-1});
			pre.pb({l%x,1});
			pre.pb({x,-1});
		}
		else{
			pre.pb({l%x,1});
			pre.pb({r%x+1,-1});
		}
	}
	sort(all(pre));
	int sum=0,ans=0,last=pre[0].ff;
	for(auto i:pre){
		if(sum>0){
			ans+=i.ff-last;
		}
		sum+=i.ss;
		last=i.ff;
	}
	cout<<ans<<endl;
}

• 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