Submission #335099

#	Time	Username	Problem	Language	Result	Execution time	Memory
335099		CSQ31	Strange Device (APIO19_strange_device)	C++14	35 / 100	831 ms	76908 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() {
	scanf("%d %lld %lld", &n, &A, &B);
	C = A / gcd(A, B + 1) * B;
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &l, &r);
		if (r - l + 1 >= C) {
			printf("%lld\n", C);
			return 0;
		}
		l %= C, r %= C;
		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;
		int y = lower_bound(temp + 1, temp + m + 1, sect[i].second + 1) - temp;
		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;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |  scanf("%d %lld %lld", &n, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |   scanf("%lld %lld", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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