Submission #445801

#	Time	Username	Problem	Language	Result	Execution time	Memory
445801		nonsensenonsense1	Strange Device (APIO19_strange_device)	C++17	100 / 100	587 ms	30032 KiB

strange_device

#include <cstdio>
#include <vector>
#include <algorithm>

long long gcd(long long a, long long b) 
{
	while (a && b) {
		if (a > b) a %= b;
		else b %= a;
	}
	return a + b;
}

int n;
long long a, b, l, r;

int main() 
{
	scanf("%d%lld%lld", &n, &a, &b);
	long long d = b % a + 1, k = a / gcd(a, d), p;
	if ((~((long long)1 << 63) >> 1) / k < b) p = ~((long long)1 << 63);
	else p = k * b;
	std::vector<std::pair<long long, long long> > s;
	for (int i = 0; i < n; ++i) {
		scanf("%lld%lld", &l, &r);
		if (r - l + 1 >= p) {
			printf("%lld\n", p);
			return 0;
		}
		l %= p;
		r %= p;
		if (l <= r) s.push_back(std::make_pair(l, r));
		else {
			s.push_back(std::make_pair(0, r));
			s.push_back(std::make_pair(l, p - 1));
		}
	}
	std::sort(s.begin(), s.end());
	long long ans = 0, l = 0, r = -1;
	for (int i = 0; i < (int)s.size(); ++i) {
		if (s[i].first <= r) {
			ans += std::max((long long)0, s[i].second - r);
			r = std::max(r, s[i].second);
		}
		else {
			ans += s[i].second - s[i].first + 1;
			l = s[i].first;
			r = s[i].second;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:39:21: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   39 |  long long ans = 0, l = 0, r = -1;
      |                     ^
strange_device.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf("%d%lld%lld", &n, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld%lld", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

• 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