oj.uz

Submission #254838

# Submission time Handle Problem Language Result Execution time Memory
254838 2020-07-30T17:37:56 Z Lawliet Strange Device (APIO19_strange_device) C++17
15 / 100
 616 ms 53540 KB 
#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 = 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 8 ms 1024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 539 ms 53312 KB Output is correct
3 Correct 530 ms 53180 KB Output is correct
4 Correct 560 ms 53320 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 539 ms 53312 KB Output is correct
3 Correct 530 ms 53180 KB Output is correct
4 Correct 560 ms 53320 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 547 ms 53252 KB Output is correct
7 Correct 587 ms 53312 KB Output is correct
8 Correct 541 ms 53312 KB Output is correct
9 Correct 610 ms 53280 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 539 ms 53312 KB Output is correct
3 Correct 530 ms 53180 KB Output is correct
4 Correct 560 ms 53320 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 52 ms 5736 KB Output is correct
7 Correct 57 ms 5760 KB Output is correct
8 Correct 49 ms 5732 KB Output is correct
9 Correct 52 ms 5740 KB Output is correct
10 Correct 53 ms 5732 KB Output is correct
11 Correct 55 ms 5736 KB Output is correct
12 Correct 52 ms 5736 KB Output is correct
13 Correct 59 ms 6108 KB Output is correct
14 Correct 52 ms 5736 KB Output is correct
15 Incorrect 58 ms 5736 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 58 ms 5736 KB Output is correct
3 Correct 55 ms 5736 KB Output is correct
4 Correct 616 ms 53540 KB Output is correct
5 Correct 53 ms 5736 KB Output is correct
6 Correct 54 ms 5732 KB Output is correct
7 Correct 55 ms 5732 KB Output is correct
8 Correct 57 ms 5732 KB Output is correct
9 Correct 54 ms 5732 KB Output is correct
10 Correct 57 ms 5736 KB Output is correct
11 Correct 58 ms 5736 KB Output is correct
12 Correct 52 ms 5732 KB Output is correct
13 Correct 57 ms 5864 KB Output is correct
14 Incorrect 571 ms 53292 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 8 ms 1024 KB Output isn't correct
3 Halted 0 ms 0 KB -