제출 #1044679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044679		vjudge1	Strange Device (APIO19_strange_device)	C++17	100 / 100	427 ms	69976 KiB

strange_device

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
	#include "debug.h"
#else 
	#define debug(...) void(23)
#endif

constexpr i64 INF = 2E18;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N;
	i64 A, B;
	std::cin >> N >> A >> B;
	std::vector<i64> L(N), R(N);
	for(int i = 0; i < N; ++i) {
		std::cin >> L[i] >> R[i];
	}

	i64 ans = 0;
	for(int i = 0; i < N; ++i) {
		ans += R[i] - L[i] + 1;
	}

	{
		i64 b = B + 1;
		i64 g = std::gcd(A, b);
		A /= g;
	}

	// B * A >= INF
	if(B >= (INF + A - 1) / A) {
		std::cout << ans << '\n';
		return 0;
	}

	i64 search = B * A;

	debug(search);

	std::vector<std::pair<i64, int>> g;
	for(int i = 0; i < N; ++i) {
		if(R[i] - L[i] + 1 >= search) {
			std::cout << search << '\n';
			return 0;
		}
		if(L[i] % search < (R[i] + 1) % search) {
			g.emplace_back(L[i] % search, +1);
			g.emplace_back((R[i] + 1) % search, -1);
		} else {
			g.emplace_back(L[i] % search, +1);
			g.emplace_back(search, -1);
			g.emplace_back(0, +1);
			g.emplace_back((R[i] + 1) % search, -1);
		}
	}

	std::sort(g.begin(), g.end());

	debug(g);

	i64 last = 0, nw = 0;
	ans = 0;
	for(auto[x, d] : g) {
		if(nw > 0) {
			debug(last, x);
			ans += x - last;
		}
		nw += d;
		last = x;
	}

	std::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