oj.uz

Submission #148077

# Submission time Handle Problem Language Result Execution time Memory
148077 2019-08-31T13:41:50 Z WhipppedCream Strange Device (APIO19_strange_device) C++17
35 / 100
 914 ms 49584 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 376 KB Output is correct
2 Correct 9 ms 1268 KB Output is correct
3 Correct 9 ms 1264 KB Output is correct
4 Correct 2 ms 296 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 292 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 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 252 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1268 KB Output is correct
17 Correct 85 ms 6388 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 376 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 2 ms 348 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 535 ms 49004 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 690 ms 48952 KB Output is correct
3 Correct 737 ms 49352 KB Output is correct
4 Correct 699 ms 49212 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 690 ms 48952 KB Output is correct
3 Correct 737 ms 49352 KB Output is correct
4 Correct 699 ms 49212 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 721 ms 49156 KB Output is correct
7 Correct 697 ms 49584 KB Output is correct
8 Correct 720 ms 49352 KB Output is correct
9 Correct 831 ms 49160 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 690 ms 48952 KB Output is correct
3 Correct 737 ms 49352 KB Output is correct
4 Correct 699 ms 49212 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 67 ms 6368 KB Output is correct
7 Correct 72 ms 6516 KB Output is correct
8 Correct 68 ms 6076 KB Output is correct
9 Correct 71 ms 6116 KB Output is correct
10 Correct 66 ms 6188 KB Output is correct
11 Correct 71 ms 6116 KB Output is correct
12 Correct 68 ms 6116 KB Output is correct
13 Correct 79 ms 6164 KB Output is correct
14 Correct 68 ms 6096 KB Output is correct
15 Correct 80 ms 6416 KB Output is correct
16 Correct 77 ms 6484 KB Output is correct
17 Correct 73 ms 6372 KB Output is correct
18 Correct 729 ms 49296 KB Output is correct
19 Correct 680 ms 49280 KB Output is correct
20 Correct 870 ms 49552 KB Output is correct
21 Correct 82 ms 6568 KB Output is correct
22 Correct 64 ms 6472 KB Output is correct
23 Correct 231 ms 22420 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 77 ms 6376 KB Output is correct
3 Correct 78 ms 6384 KB Output is correct
4 Correct 914 ms 49168 KB Output is correct
5 Correct 76 ms 6192 KB Output is correct
6 Correct 77 ms 6108 KB Output is correct
7 Correct 79 ms 6172 KB Output is correct
8 Correct 80 ms 6120 KB Output is correct
9 Correct 77 ms 6116 KB Output is correct
10 Correct 84 ms 6116 KB Output is correct
11 Correct 82 ms 6372 KB Output is correct
12 Correct 75 ms 6344 KB Output is correct
13 Correct 80 ms 6372 KB Output is correct
14 Correct 865 ms 49428 KB Output is correct
15 Correct 82 ms 6500 KB Output is correct
16 Correct 712 ms 49356 KB Output is correct
17 Correct 706 ms 49256 KB Output is correct
18 Incorrect 0 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 9 ms 1268 KB Output is correct
3 Correct 9 ms 1264 KB Output is correct
4 Correct 2 ms 296 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 292 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 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 252 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1268 KB Output is correct
17 Correct 85 ms 6388 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct