Submission #210742

#	Time	Username	Problem	Language	Result	Execution time	Memory
210742		islingr	Strange Device (APIO19_strange_device)	C++14	100 / 100	2248 ms	30968 KiB

strange_device

/*
	22/02/2020
	islingr
*/

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

#define all(x) begin(x), end(x)
#define eb(x...) emplace_back(x)

using ll = int64_t;

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

struct event {
	ll l, r;
	event(ll a, ll b) : l{a}, r{b} { }
	bool operator<(const event &e) const { return r < e.r; }
};

const ll inf = 1e18;

ll solve () {
	int n; ll a, b; cin >> n >> a >> b;
	ll g = __gcd(a, b + 1), p;
	if (a / g > inf / b) p = inf;
	else p = a / g * b;

	vector<event> v; v.reserve(2 * n);
	rep(i, 0, n) {
		ll l, r; cin >> l >> r;
		if (r - l + 1 < p) {
			l %= p; r %= p;
			if (l <= r) v.eb(l, r);
			else v.eb(0, r), v.eb(l, p - 1);
		} else return p;
	}
	sort(all(v));
	ll ans = 0;
	while (!v.empty()) {
		event top = v.back(); v.pop_back();
		while (!v.empty() && top.l <= v.back().r) {
			ckmin(top.l, v.back().l);
			v.pop_back();
		}
		ans += top.r - top.l + 1;
	}
	return ans;
}

signed main() { cout << solve(); }

• 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