제출 #372475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372475		peijar	이상한 기계 (APIO19_strange_device)	C++17	65 / 100	656 ms	34972 KiB

strange_device

#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;

using ll = long long;

template<typename... Args>
void read(Args&... args)
{
	((cin >> args), ...);
}
template<typename T>
void read(vector<T> &vec)
{
	for (auto &v : vec) read(v);
}

void write() {}
template<typename H, typename... T>
void write(const H &h, const T&... t)
{
	cout << h;
	if (sizeof...(t)) {cout << ' '; write(t...);}
}

template<typename T>
void write(const vector<T> &vec)
{
	if (SZ(vec) == 0) return;
	write(vec[0]);
	for (int i(1); i < SZ(vec); ++i)
	{cout << ' '; write(vec[i]);}
}

template<typename... Args>
void writeln(Args... args)
{
	write(args...); cout << '\n';
}

void show(__int128 x)
{
	if (x >= 10)
		show(x/10);
	cout << int(x%10);
}

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

	int n;
	ll _A, _B;
	using T = __int128;
	read(n, _A, _B);
	T A(_A), B(_B);
	__int128 mod = (A  * B) / gcd(_A, _B+1);

	vector<pair<T, T>> intervals;
	for (int i(0); i < n; ++i)
	{
		ll _l, _r;
		read(_l, _r);
		T l(_l), r(_r);
		l %= mod, r %= mod;
		if (l > r)
		{
			intervals.emplace_back(l, mod-1);
			intervals.emplace_back(0, r);
		}
		else
			intervals.emplace_back(l, r);
	}
	sort(intervals.begin(), intervals.end());
	T lst(-1);
	T sol(0);
	for (auto [l, r] : intervals)
	{
		sol += max(T(0), r - max(l, lst+1) + 1);
		lst = max(lst, r);
	}
	show(sol);
	cout << endl;
}

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