Submission #497796

#	Time	Username	Problem	Language	Result	Execution time	Memory
497796		MilosMilutinovic	Strange Device (APIO19_strange_device)	C++14	100 / 100	643 ms	86224 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
ll A, B;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(11);
	cerr << fixed << setprecision(6);

	cin >> n >> A >> B;
	A /= __gcd(A, B + 1);
	ll mod = 1e18 + 1;
	if (A <= (LLONG_MAX / 2) / B) mod = A * B;
	vector<pair<ll, ll>> vec;
	for (int i = 0; i < n; ++i) {
		ll l, r;
		cin >> l >> r;
		ll len = r - l + 1;
		if (len >= mod) {
			cout << mod << "\n";
			return 0;
		}
		l = l % mod;
		r = r % mod;
		if (l <= r) {
			vec.push_back({l, r});
		} else {
			vec.push_back({l, mod - 1});
			vec.push_back({0, r});
		}
	}

	vector<pair<ll, int>> Events;
	for (int i = 0; i < vec.size(); ++i) {
		Events.push_back({vec[i].first, 0});
		Events.push_back({vec[i].second, 1});
	}

	sort(Events.begin(), Events.end());

	int bal = 0;
	ll left = 0, tot = 0;
	for (auto ev : Events) {
		if (ev.second == 0) {
			bal++;
			if (bal == 1) left = ev.first;
		} else {
			bal--;
			if (bal == 0) tot += ev.first - left + 1;
		}
	}
	cout << tot << "\n";
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < vec.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