oj.uz

Submission #677765

# Submission time Handle Problem Language Result Execution time Memory
677765 2023-01-04T10:32:46 Z parsadox2 Strange Device (APIO19_strange_device) C++14
10 / 100
 354 ms 32272 KB 
#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define int long long 
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 10 , inf = 1e18;
int n , A , B , l[maxn] , r[maxn];

int gcd(int a , int b)
{
	if(b == 0)
		return a;
	return gcd(b , a % b);
}

int32_t main()
{
	fast;
	cin >> n >> A >> B;
	int S = 0;
	for(int i = 0 ; i < n ; i++)
	{
		cin >> l[i] >> r[i];
		S += r[i] - l[i] + 1;
	}
	int g = gcd(A , B + 1);
	A /= g;
	if(inf / A < B)
	{
		cout << S << endl;
		return 0;
	}
	A *= B;
	map <int , int> mp;
	if(S > maxn)
	{
		cout << 667 << endl;
		return 0;
	}
	int ans = 0;
	for(int i = 0 ; i < n ; i++)
	{
		for(int j = l[i] ; j <= r[i] ; j++)
		{
			if(mp[(j % A)] == 0)
			{
				mp[(j % A)] = 667;
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 54 ms 12888 KB Output is correct
3 Correct 89 ms 18484 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 8 ms 1140 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 34 ms 7012 KB Output is correct
16 Correct 31 ms 7260 KB Output is correct
17 Correct 63 ms 11836 KB Output is correct
18 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 131 ms 32272 KB Output is correct
3 Correct 127 ms 32072 KB Output is correct
4 Correct 149 ms 30584 KB Output is correct
5 Incorrect 239 ms 16652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 54 ms 12888 KB Output is correct
3 Correct 89 ms 18484 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 8 ms 1140 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 34 ms 7012 KB Output is correct
16 Correct 31 ms 7260 KB Output is correct
17 Correct 63 ms 11836 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Halted 0 ms 0 KB -