제출 #1059826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059826		dpsaveslives	이상한 기계 (APIO19_strange_device)	C++17	35 / 100	1198 ms	45676 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6;
int n, m, tot, sum[maxn + 3];
ll A, B, C, l, r, temp[maxn + 3];
pair<ll, ll> sect[maxn + 3];
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
int main() {
	cin >> n >> A >> B;
	C = A / gcd(A, B + 1) * B; //AB/gcd(A,B+1)
	for (int i = 1; i <= n; i++) {
		cin >> l >> r;
		if (r - l + 1 >= C) {
			cout << C << "\n";
			return 0;
		}
		l %= C, r %= C; //"how far they are into" the cycle they are in (I feel so stupid for not seeing that all you need to do is %)
		if (l <= r) {
			sect[++tot] = make_pair(l, r);
		} else {
			sect[++tot] = make_pair(0, r);
			sect[++tot] = make_pair(l, C - 1);
		}
	}
	for (int i = 1; i <= tot; i++) {
		temp[++m] = sect[i].first;
		temp[++m] = sect[i].second + 1;
	}
	sort(temp + 1, temp + m + 1);
	for (int i = 1; i <= tot; i++) {
		int x = lower_bound(temp + 1, temp + m + 1, sect[i].first) - temp; //find the one that ends first that starts with sect[i].first
		int y = lower_bound(temp + 1, temp + m + 1, sect[i].second + 1) - temp; //find the first one that is >= sect[i].second+1
		sum[x]++, sum[y]--;
	}
	ll ans = 0;
	for (int i = 1; i <= m; i++) {
		sum[i] += sum[i - 1];
		if (sum[i]) {
			ans += temp[i + 1] - temp[i];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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