Submission #124493

#	Time	Username	Problem	Language	Result	Execution time	Memory
124493		TadijaSebez	Strange Device (APIO19_strange_device)	C++11	100 / 100	986 ms	51284 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll inf=9e18;
const int N=1000050;
ll l[N],r[N];
int main()
{
	int n;
	ll A,B;
	scanf("%i %lld %lld",&n,&A,&B);
	for(int i=1;i<=n;i++) scanf("%lld %lld",&l[i],&r[i]);
	ll x=A/__gcd(A,B+1);
	if(inf/x>B)
	{
		ll P=x*B;
		//printf("P:%lld\n",P);
		bool all=0;
		vector<pair<ll,int>> evs;
		for(int i=1;i<=n;i++)
		{
			if(r[i]-l[i]+1>=P) all=1;
			r[i]%=P;
			l[i]%=P;
			if(r[i]<l[i]) evs.pb({0,1}),evs.pb({P,-1});
			evs.pb({l[i],1});
			evs.pb({r[i]+1,-1});
		}
		if(all) printf("%lld\n",P);
		else
		{
			int cur=0;
			sort(evs.begin(),evs.end());
			ll ltm=-1,ans=0;
			for(pair<ll,int> e:evs)
			{
				ll tme=e.first-ltm;
				//printf("(%lld - %lld) cur:%i\n",ltm,e.first,cur);
				ltm=e.first;
				if(cur) ans+=tme;
				cur+=e.second;
			}
			printf("%lld\n",ans);
		}
	}
	else
	{
		ll sum=0;
		for(int i=1;i<=n;i++) sum+=r[i]-l[i]+1;
		printf("%lld\n",sum);
	}
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %lld %lld",&n,&A,&B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:13:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lld %lld",&l[i],&r[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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