oj.uz

Submission #126587

# Submission time Handle Problem Language Result Execution time Memory
126587 2019-07-08T07:03:38 Z roseanne_pcy Strange Device (APIO19_strange_device) C++14
35 / 100
 911 ms 49196 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e6+5;
ll L[maxn], R[maxn];

vector< pair<ll, int> > sw;

int main()
{
	int n;
	ll A, B;
	scanf("%d %lld %lld", &n, &A, &B);
	ll k = A/__gcd(A, B+1);
	bool over = false;
	if(k*B/B != k) over = true;
	ll len = 0;
	for(int i = 1; i<= n; i++)
	{
		scanf("%lld %lld", &L[i], &R[i]);
		len += (R[i]-L[i]+1);
	}
	if(over)
	{
		printf("%lld\n", len);
		return 0;
	}
	for(int i = 1; i<= n; i++)
	{
		ll tmp = R[i]-L[i]+1;
		if(tmp>= k*B)
		{
			printf("%lld\n", k*B);
			return 0;
		}
		ll m1 = L[i]%(k*B);
		ll m2 = R[i]%(k*B);
		if(m1<= m2) 
		{
			sw.pb({m1, 1});
			sw.pb({m2+1, -1});
		}
		else
		{
			sw.pb({m1, 1});
			sw.pb({k*B, -1});
			sw.pb({0, 1});
			sw.pb({m2+1, -1});
		}
	}
	sort(sw.begin(), sw.end());
	ll ans = 0;
	int run = 0;
	for(int i = 0; i+1< (int) sw.size(); i++)
	{
		run += sw[i].Y;
		if(run> 0)
		{
			ans += sw[i+1].X-sw[i].X;
		}
	}
	printf("%lld\n", ans);
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %lld", &n, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &L[i], &R[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 10 ms 1268 KB Output is correct
3 Correct 9 ms 1268 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 252 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1268 KB Output is correct
17 Correct 84 ms 6376 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 252 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 728 ms 49096 KB Output is correct
3 Correct 761 ms 49048 KB Output is correct
4 Correct 731 ms 49164 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 728 ms 49096 KB Output is correct
3 Correct 761 ms 49048 KB Output is correct
4 Correct 731 ms 49164 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 731 ms 49164 KB Output is correct
7 Correct 724 ms 49196 KB Output is correct
8 Correct 718 ms 49068 KB Output is correct
9 Correct 870 ms 49124 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 728 ms 49096 KB Output is correct
3 Correct 761 ms 49048 KB Output is correct
4 Correct 731 ms 49164 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 71 ms 6856 KB Output is correct
7 Correct 75 ms 6760 KB Output is correct
8 Correct 70 ms 6800 KB Output is correct
9 Correct 74 ms 6828 KB Output is correct
10 Correct 68 ms 6744 KB Output is correct
11 Correct 76 ms 6400 KB Output is correct
12 Correct 68 ms 6372 KB Output is correct
13 Correct 79 ms 6340 KB Output is correct
14 Correct 70 ms 6380 KB Output is correct
15 Correct 83 ms 6344 KB Output is correct
16 Correct 80 ms 6372 KB Output is correct
17 Correct 73 ms 6372 KB Output is correct
18 Correct 759 ms 49112 KB Output is correct
19 Correct 683 ms 49104 KB Output is correct
20 Correct 861 ms 49088 KB Output is correct
21 Correct 81 ms 6392 KB Output is correct
22 Correct 63 ms 6372 KB Output is correct
23 Correct 233 ms 22480 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 79 ms 6368 KB Output is correct
3 Correct 80 ms 6632 KB Output is correct
4 Correct 911 ms 49032 KB Output is correct
5 Correct 79 ms 6376 KB Output is correct
6 Correct 77 ms 6376 KB Output is correct
7 Correct 79 ms 6384 KB Output is correct
8 Correct 80 ms 6344 KB Output is correct
9 Correct 76 ms 6372 KB Output is correct
10 Correct 86 ms 6548 KB Output is correct
11 Correct 108 ms 6372 KB Output is correct
12 Correct 76 ms 6372 KB Output is correct
13 Correct 87 ms 6436 KB Output is correct
14 Correct 875 ms 49044 KB Output is correct
15 Correct 83 ms 6372 KB Output is correct
16 Correct 702 ms 49104 KB Output is correct
17 Correct 738 ms 49084 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 10 ms 1268 KB Output is correct
3 Correct 9 ms 1268 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 252 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1268 KB Output is correct
17 Correct 84 ms 6376 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct