oj.uz

Submission #254840

# Submission time Handle Problem Language Result Execution time Memory
254840 2020-07-30T17:41:25 Z Lawliet Strange Device (APIO19_strange_device) C++17
15 / 100
 556 ms 17492 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 = 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

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 1 ms 256 KB Output is correct
2 Incorrect 6 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 1 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 1 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 518 ms 17488 KB Output is correct
3 Correct 497 ms 17368 KB Output is correct
4 Correct 495 ms 17492 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 518 ms 17488 KB Output is correct
3 Correct 497 ms 17368 KB Output is correct
4 Correct 495 ms 17492 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 500 ms 17488 KB Output is correct
7 Correct 512 ms 17360 KB Output is correct
8 Correct 496 ms 17360 KB Output is correct
9 Correct 531 ms 17360 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 518 ms 17488 KB Output is correct
3 Correct 497 ms 17368 KB Output is correct
4 Correct 495 ms 17492 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 54 ms 5736 KB Output is correct
7 Correct 56 ms 5736 KB Output is correct
8 Correct 50 ms 5736 KB Output is correct
9 Correct 52 ms 5736 KB Output is correct
10 Correct 54 ms 5732 KB Output is correct
11 Correct 54 ms 5736 KB Output is correct
12 Correct 50 ms 5736 KB Output is correct
13 Correct 53 ms 5736 KB Output is correct
14 Correct 50 ms 5736 KB Output is correct
15 Incorrect 57 ms 5732 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 56 ms 5732 KB Output is correct
3 Correct 54 ms 5736 KB Output is correct
4 Correct 556 ms 17184 KB Output is correct
5 Correct 53 ms 5228 KB Output is correct
6 Correct 52 ms 5228 KB Output is correct
7 Correct 56 ms 5232 KB Output is correct
8 Correct 54 ms 5228 KB Output is correct
9 Correct 53 ms 5228 KB Output is correct
10 Correct 63 ms 5228 KB Output is correct
11 Correct 53 ms 5228 KB Output is correct
12 Correct 46 ms 5108 KB Output is correct
13 Correct 54 ms 5104 KB Output is correct
14 Incorrect 543 ms 17104 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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