Submission #947346

#	Time	Username	Problem	Language	Result	Execution time	Memory
947346		MinaRagy06	Strange Device (APIO19_strange_device)	C++17	100 / 100	586 ms	73496 KiB

strange_device

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

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	ll a, b;
	cin >> n >> a >> b;
	ll m;
	if (a / gcd(a, b + 1) <= (ll) 2e18 / b) {
		m = a * b / gcd(a, b + 1);
	} else {
		m = 2e18;
	}
	array<ll, 2> q[n];
	vector<ll> v = {0, m};
	for (int i = 0; i < n; i++) {
		auto &[l, r] = q[i];
		cin >> l >> r;
		if (r - l >= m) {
			cout << m << '\n';
			return 0;
		}
		ll s = l % m, e = r % m;
		v.push_back(s);
		v.push_back(e + 1);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	int toadd[v.size()]{};
	auto add2 = [&] (ll x, int y) {
		int p = lower_bound(v.begin(), v.end(), x) - v.begin();
		toadd[p] += y;
	};
	auto add = [&] (ll l, ll r) {
		add2(l, 1);
		add2(r + 1, -1);
	};
	for (int i = 0; i < n; i++) {
		auto &[l, r] = q[i];
		ll s = l % m, e = r % m;
		if (e - s == r - l) {
			add(s, e);
			continue;
		}
		add(s, m - 1);
		add(0, e);
	}
	int cnt = 0;
	ll ans = 0;
	for (int i = 0; i < v.size(); i++) {
		if (cnt) {
			ans += v[i] - v[i - 1];
		}
		cnt += toadd[i];
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

• 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