Submission #721461

#	Time	Username	Problem	Language	Result	Execution time	Memory
721461		alvingogo	Strange Device (APIO19_strange_device)	C++14	100 / 100	578 ms	53288 KiB

strange_device

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

long long inf=2e18;
long long mul(long long x,long long y){	
	long long sum=inf;
	if(sum/x>=y-2){
		sum=min(sum,x*y);
	}
	return sum;
}
int main(){
    AquA;
	long long n,a,b;
	cin >> n >> a >> b;
	long long u=__gcd(a,(b+1));
	a/=u;
	long long sum=mul(a,b);
	vector<pair<long long,long long> > x;
	for(int i=0;i<n;i++){
		long long l,r;
		cin >> l >> r;
		if(r/sum>l/sum+1){
			cout << sum << "\n";
			return 0;
		}
		if(r/sum==l/sum){
			x.push_back({l%sum,r%sum});
		}
		else{
			x.push_back({l%sum,sum-1});
			x.push_back({0%sum,r%sum});
		}
	}
	sort(x.begin(),x.end());
	long long ans=0;
	long long nw=0;
	for(auto h:x){
		nw=max(nw,h.fs);
		if(h.sc>=nw){
			ans+=(h.sc-nw+1);
		}
		nw=max(nw,h.sc+1);
	}
	cout << ans << "\n";
    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