Submission #677765

#	Time	Username	Problem	Language	Result	Execution time	Memory
677765		parsadox2	Strange Device (APIO19_strange_device)	C++14	10 / 100	354 ms	32272 KiB

strange_device

#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 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30