Submission #137009

#	Time	Username	Problem	Language	Result	Execution time	Memory
137009		arthurconmy	Strange Device (APIO19_strange_device)	C++14	100 / 100	724 ms	43396 KiB

strange_device

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPb(j, d, c) for (int j = int(d); j >= int(c); j--)
#define ff first
#define ss second
#define pb push_back
#define len(x) int((x).size())

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	//ifstream cin("input.txt");
	//ifstream cin("test.in");
	//ofstream cout("test.out");

	ll n,a,b;
	cin>>n>>a>>b;	

	vector<pll> segs;

	ll s=0;

	REP(i,1,n)
	{
		ll l,r;
		cin>>l>>r;

		segs.pb({l,r});

		s+=r-l+1;
	}

	// if(s<=1e6 && false) // REMOVE THIS!!!
	// {
	// 	// brute force

	// 	vector<pll> pairs;

	// 	for(auto seg:segs)
	// 	{
	// 		for(ll i=seg.ff; i<=seg.ss; i++)
	// 		{
	// 			pairs.pb({(i+ll(i/b))%a,i%b});
	// 		}
	// 	}

	// 	sort(pairs.begin(),pairs.end());

	// 	ll ans=1;

	// 	REP(i,1,len(pairs)-1)
	// 	{
	// 		if(pairs[i]!=pairs[i-1]) ans++;
	// 	}

	// 	cout << ans << endl;
	// 	return 0;
	// }

	ll l=segs[0].ff;
	ll r=segs[0].ss;

	ll k = a/__gcd(a,b+1);
	
	// cout << k << endl;

	// we want to know when kB >= 1e18

	if(log(k) + log(b) >= 18*log(10))
	{
		cout << s << endl;
		return 0;
	}

	else
	{
		k*=b;

		vector<pll> intervals;

		for(auto seg:segs)
		{
			if(seg.ss-seg.ff+1 >= k)
			{
				cout << k << endl;
				return 0;
			}

			if(seg.ff%k > seg.ss%k)
			{
				intervals.pb({0,seg.ss%k});
				intervals.pb({seg.ff%k,k-1});
			}

			else
			{
				intervals.pb({seg.ff%k,seg.ss%k});
			}
		}

		sort(intervals.begin(),intervals.end());

		ll cur_start=intervals[0].ff;
		ll cur_end=intervals[0].ss;

		ll ans=0;

		REP(i,1,len(intervals)-1)
		{
			if(intervals[i].ff > cur_end+1)
			{
				ans += cur_end-cur_start+1;
				cur_start=intervals[i].ff;
				cur_end=intervals[i].ss;
			}

			else
			{
				cur_end=max(cur_end,intervals[i].ss);
			}
		}

		ans += cur_end-cur_start+1;

		cout << ans << endl;
	}
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:82:5: warning: unused variable 'l' [-Wunused-variable]
  ll l=segs[0].ff;
     ^
strange_device.cpp:83:5: warning: unused variable 'r' [-Wunused-variable]
  ll r=segs[0].ss;
     ^

• 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