Submission #579497

#	Time	Username	Problem	Language	Result	Execution time	Memory
579497		joshjms	Strange Device (APIO19_strange_device)	C++17	100 / 100	851 ms	163824 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
	cin.tie(0) -> ios_base::sync_with_stdio(0);
 
	ll n, a, b;
	cin >> n >> a >> b;
 
	if(a > 1e18 / b)
	{
		ll sum = 0;
		for(int i = 0; i < n; i++)
		{
			ll l, r;
			cin >> l >> r;
			sum += r - l + 1;
		}
 
		cout << sum;
	}
	else
	{
		ll g = a * b / gcd(a, b + 1);
 
		map<ll, vector<ll>> M;
		for(int i = 0; i < n; i++)
		{
			ll l, r;
			cin >> l >> r;
          
          	if(r - l + 1 >= g) {
              cout << g << "\n";
              return 0;
			}
			l %= g, r %= g;
			if(r < l)
			{
				M[0].push_back(r);
				M[l].push_back(g - 1);
			}
			else
			{
				M[l].push_back(r);
			}
		}
	 
		multiset<ll> S;
		vector<pair<ll,ll>> intervals;
	 
		ll begin = 2e18, last = 0;
		for(auto &[st, v] : M)
		{	
			
			while(!S.empty() && *S.begin() < st)
			{
				S.erase(S.begin());
			}
	 
			if(S.empty() && begin != 2e18)
			{
				intervals.push_back({begin, last});
				begin = 2e18;
				last = 0;
			}
	 
			begin = min(begin, st);
	 
			for(auto i : v)
			{
				S.insert(i);
				last = max(last, i);
			}
	 
		}
	 
		if(!S.empty() && begin != 2e18)
		{
			while(!S.empty())
			{
				last = max(last, *S.begin());
				S.erase(S.begin());
			}
	 
			intervals.push_back({begin, last});
		}
	 
		long long ans = 0;
		for(auto [l, r] : intervals) 
		{
			ans += r - l + 1;
		}
		cout << ans;
	}
 
	
 
}

• 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