Submission #372472

#	Time	Username	Problem	Language	Result	Execution time	Memory
372472		peijar	Strange Device (APIO19_strange_device)	C++17	65 / 100	567 ms	53552 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';
}

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

	int n;
	ll A, B;
	read(n, A, B);
	ll mod = (A  * B) / gcd(A, B+1);

	vector<pair<ll, ll>> intervals;
	for (int i(0); i < n; ++i)
	{
		ll l, r;
		read(l, 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());
	ll lst(-1);
	ll sol(0);
	for (auto [l, r] : intervals)
	{
		sol += max(0LL, r - max(l, lst+1) + 1);
		lst = max(lst, r);
	}
	writeln(sol);
}

• 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