Submission #977112

#	Time	Username	Problem	Language	Result	Execution time	Memory
977112		Batorgil952	Strange Device (APIO19_strange_device)	C++14	100 / 100	404 ms	18804 KiB

strange_device

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
 
using namespace std;
 
ll GCD(ll x, ll y){
	while(x*y!=0){
		if(x>y) x%=y;
		else y%=x;
	}
	return x+y;
}
 
int main(){
	ll n, i, A, B, l, r, k, m, ma, ans, vn;
	vector< pair< ll, ll > > v;
	
	scanf("%lld",&n);
	scanf("%lld",&A);
	scanf("%lld",&B);
	
	m=GCD(B+1, A);
	A/=m;
	ma=1000000000000000002;
	if(ma/A<B){
		k=ma;
	}
	else{
		k=A*B;
	}
//	cout<<k<<endl;
	
	ans=0;
	for(i=1; i<=n; i++){
		scanf("%lld",&l);
		scanf("%lld",&r);
		if(r-l+1>=k){
			ans=k;
		}
		if(l%k<=r%k) v.pb(mp(l%k, r%k));
		else{
			v.pb(mp(l%k, k-1));
			v.pb(mp(0, r%k));
		}
	}
	
	
	if(ans==k){
		printf("%lld\n", k);
		return 0;
	}
	sort(v.begin(), v.end());
	
	l=v[0].ff;
	r=v[0].ss;
	vn=v.size();
	for(i=1; i<vn; i++){
		if(v[i].ff<=r){
			r=max(r, v[i].ss);
		}
		else{
			ans+=(r-l+1);
			l=v[i].ff;
			r=v[i].ss;
		}
	}
	ans+=(r-l+1);
	
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
strange_device.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%lld",&A);
      |  ~~~~~^~~~~~~~~~~
strange_device.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%lld",&B);
      |  ~~~~~^~~~~~~~~~~
strange_device.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%lld",&l);
      |   ~~~~~^~~~~~~~~~~
strange_device.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%lld",&r);
      |   ~~~~~^~~~~~~~~~~

• 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