Submission #677775

#	Time	Username	Problem	Language	Result	Execution time	Memory
677775		parsadox2	Strange Device (APIO19_strange_device)	C++14	100 / 100	864 ms	115796 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];
set <pair <int , int> > st;
int gcd(int a , int b)
{
	if(b == 0)
		return a;
	return gcd(b , a % b);
}

void add (int L , int R)
{
	if(st.empty())
	{
		st.insert(make_pair(L , R));
		return;
	}
	auto it = st.upper_bound({L , L});
	if(it != st.begin())
		it--;
	auto v = *it;
	if(v.S < L)
		it++;
	if(it == st.end())
	{
		st.insert({L , R});
		return;
	}
	auto u = *it;
	L = min(u.F , L);
	vector <pair <int, int>> vec;
	while(u.F <= R)
	{
		vec.pb(u);
		it++;
		if(it == st.end())
			break;
		u = *it;
	}
	if(!vec.empty())
	{
		R = max(R , vec.back().S);
	}
	for(auto u : vec)
		st.erase(u);
	st.insert({L , R});
}

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;
	for(int i = 0 ; i < n ; i++)
	{
		int tmp = l[i] / A;
		tmp = tmp * A;
		l[i] -= tmp;
		r[i] -= tmp;
		add(l[i] , min(r[i] , A - 1));
		if(r[i] >= A)
		{
			r[i] -= A;
			add(0 , min(A - 1 , r[i]));
		}
	}
	int ans = 0;
	for(auto u : st)
	{
		ans += u.S - u.F + 1;
	}
	cout << ans << endl;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30