Submission #254840

#	Time	Username	Problem	Language	Result	Execution time	Memory
254840		Lawliet	Strange Device (APIO19_strange_device)	C++17	15 / 100	556 ms	17492 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 lastR = -2;

	for(int i = 0 ; i < (int)sweep.size() ; i++)
	{
		if( lastR + 1 < sweep[i].first ) merged.push_back( sweep[i] );
		else merged.back().second = sweep[i].second;

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

	lli ans = 0;

	for(int i = 0 ; i < (int)merged.size() ; i++)
		ans += merged[i].second - merged[i].first + 1;

	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: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30