제출 #1044980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044980		Kel_Mahmut	이상한 기계 (APIO19_strange_device)	C++14	100 / 100	1240 ms	168156 KiB

strange_device

#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

ll ggcd(ll a, ll b){
	if(b == 0) return a;
	return ggcd(b, a % b);
}

const ll inf = ll(1e18) + 1;

int main(){
	ll n, a, b;
	cin >> n >> a >> b;
	vector<pair<ll, ll>> v(n);
	ll mx = 0;
	for(int i = 0; i < n; i++){
		ll l, r;
		cin >> l >> r;
		v[i] = {l, r};
		mx = max(mx, r);
	}

	ll g = ggcd(a, b + 1);
	ll sade = a / g;
	ll mod;
	if(double(sade) * double(b) >= double(inf)){
		mod = inf;
	}
	else mod = sade * b;
	multiset<pair<ll, int>> s;
	for(int i = 0; i < n; i++){
		ll tl = v[i].first;
		ll tr = v[i].second;
		ll sub = tl / mod;
		tl -= sub * mod;
		tr -= sub * mod;
		if(tr - tl + 1 >= mod){
			cout << mod << endl;
			exit(0);
		}
		if(tr >= mod){
			s.insert({0, 0});
			s.insert({tr - mod, 1});
			s.insert({mod - 1, 1});
			s.insert({tl, 0});
		}
		else{
			s.insert({tl, 0});
			s.insert({tr, 1});
		}
	}

	ll ans = 0;
	int cnt = 0;
	ll beg = -1;
	for(auto it = s.begin(); it != s.end(); it++){
		if(it->second == 0 && cnt == 0){
			beg = it->first;
		}
		if(it->second == 0){
			cnt++;
		}
		if(it->second == 1 && cnt == 1){
			ans += it->first - beg + 1;
		}
		if(it->second == 1)
			cnt--;
	}
	cout << ans << endl;
}

• 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