Submission #447460

#	Time	Username	Problem	Language	Result	Execution time	Memory
447460		S2speed	Strange Device (APIO19_strange_device)	C++17	100 / 100	779 ms	34132 KiB

strange_device

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 1e6 + 16 , inf = 2e18;

vector<pll> v;

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

	ll n , a , b , h;
	cin>>n>>a>>b;
	__int128_t q = (__int128_t)1 * a * b / __gcd(a , b + 1);
	h = min((__int128_t)(inf) , q);
	for(ll i = 0 ; i < n ; i++){
		ll l , r;
		cin>>l>>r; r++;
		if(r - l >= h){
			cout<<h<<'\n';
			return 0;
		}
		l %= h;
		r %= h;
		v.push_back({l , 1});
		v.push_back({r , -1});
		if(r < l){
			v.push_back({0 , 1});
			v.push_back({h , -1});
		}
	}
	sort(all(v));
	ll pr = 0 , cnt = 0 , ans = 0;
	ll vs = sze(v);
	for(ll i = 0 ; i < vs ; i++){
		ll cur = v[i].first;
		ans += (cnt > 0) * (cur - pr);
		pr = cur;
		cnt += v[i].second;
	}
	cout<<ans<<'\n';
	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