Submission #527463

#	Time	Username	Problem	Language	Result	Execution time	Memory
527463		LucaDantas	Strange Device (APIO19_strange_device)	C++17	100 / 100	526 ms	23732 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

int main() {
	long long n, A, B; scanf("%lld %lld %lld", &n, &A, &B);
	long long g = __gcd(A, B+1), sz = 0;
	if(log(A) + log(B) - log(g) > log(inf)) sz = inf;
	else sz = (A/g) * B;
	vector<pair<long long, long long>> pares;
	long long ini = 0, fim = -1, ans = 0;
	for(int i = 0; i < n; i++) {
		long long l, r; scanf("%lld %lld", &l, &r);
		if(r - l + 1 >= sz) return printf("%lld\n", sz), 0;
		l %= sz, r %= sz;
		if(r < l) fim = max(fim, r), pares.push_back({l, sz-1});
		else pares.push_back({l, r});
	}
	sort(pares.begin(), pares.end());
	for(auto p : pares) {
		if(p.first > fim) ans += fim - ini+1, ini = p.first, fim = p.second;
		else fim = max(fim, p.second);
	}
	printf("%lld\n", ans + fim - ini + 1);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:7:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  long long n, A, B; scanf("%lld %lld %lld", &n, &A, &B);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:14:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   long long l, r; 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