Submission #254847

#	Time	Username	Problem	Language	Result	Execution time	Memory
254847		Lawliet	Strange Device (APIO19_strange_device)	C++17	100 / 100	623 ms	53480 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pll;

lli n, A, B;

vector<pll> sweep;
vector<pll> merged;

int main()
{
	scanf("%lld %lld %lld",&n,&A,&B);

	lli cycleSize = A/__gcd( A , B + 1 );
	lli periodSize = 1000000000000000000LL;

	if( cycleSize <= periodSize/B )
		periodSize = cycleSize*B;

	for(int i = 1 ; i <= n ; i++)
	{
		lli L, R;
		scanf("%lld %lld",&L,&R);

		if( R - L + 1 >= periodSize )
		{
			printf("%lld\n",periodSize);
			return 0;
		}

		L %= periodSize; R %= periodSize;

		if( L <= R ) sweep.push_back( { L , R } );
		else
		{
			sweep.push_back( { 0 , R } );
			sweep.push_back( { L , periodSize - 1 } );
		}
	}

	sort( sweep.begin() , sweep.end() );

	lli ans = 0;
	lli last = -1;

	for(int i = 0 ; i < (int)sweep.size() ; i++)
	{
		last = max( last , sweep[i].first - 1 );

		if( last <= sweep[i].second )
			ans += sweep[i].second - last;

		last = max( last , sweep[i].second );
	}

	printf("%lld\n",ans);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&A,&B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&L,&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