Submission #677268

#	Time	Username	Problem	Language	Result	Execution time	Memory
677268		amirhoseinfar1385	Strange Device (APIO19_strange_device)	C++17	100 / 100	948 ms	65024 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
long long inf=1e18+10;

long long mul(long long a,long long b){
	if(inf/a<b){
		return inf;
	}
	else{
		long long ret=1ll*a*b;
		return ret;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long n;
	long long a,b;
	cin>>n>>a>>b;
	long long e=mul(a/gcd(a,(b+1)),b);
	map<long long ,long long>mp;
	for(int i=0;i<n;i++){
		long long l,r;
		cin>>l>>r;
		if(r-l+1>=e){
			cout<<e<<"\n";
			return 0;
		}
		l%=e;
		r%=e;
	//	cout<<l<<" "<<r<<endl;
		mp[l]++;
		if(l>r){
			mp[e]--;
			mp[0]++;
		}
		mp[r+1]--;
	}
	long long last=0;
	for(auto x:mp){
		mp[x.first]+=last;
		last=mp[x.first];
	}
	long long res=0;
	long long ll=0,rr=0,f=0;
	for(auto x:mp){
		rr=x.first;
		if(x.second==0){
	//	    cout<<rr<<" "<<ll<<" "<<x.first<<endl;
			res+=rr-ll;
			ll=rr;
			f=0;
		}
		else{
			if(f==0){
				ll=x.first;
				f=1;
			}
		}
	}
	cout<<res<<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