Submission #959307

#	Time	Username	Problem	Language	Result	Execution time	Memory
959307		NK_	Strange Device (APIO19_strange_device)	C++17	35 / 100	581 ms	65524 KiB

strange_device

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using vl = V<ll>;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; ll A, B; cin >> N >> A >> B;

	ll C = 1LL + (B % A);

	ll K = A / __gcd(C, A) * B;

	V<array<ll, 2>> E;
	auto add = [&](ll l, ll r) {
		E.pb(array<ll, 2>{l, +1});
		E.pb(array<ll, 2>{r + 1, -1});
	};

	for(int i = 0; i < N; i++) {
		ll l, r; cin >> l >> r;

		ll len = r - l + 1;
		if (len >= K) add(0, K - 1);
		else {
			l %= K, r %= K;
			if (l <= r) add(l, r);
			else add(l, K - 1), add(0, r);
		}

	}

	int have = 0; ll ans = 0;
	sort(begin(E), end(E));

	for(int i = 0; i < sz(E); i++) {
		int j = i; while(j < sz(E) && E[j][0] == E[i][0]) {
			have += E[j][1]; j++;
		}

		if (have && j < sz(E)) {
			ll amt = E[j][0] - E[i][0];
			// cout << E[j][0] << " " << E[i][0] << endl;
			ans += amt;
		}

		i = j - 1;
	}

	cout << ans << nl;
	
	exit(0-0);
}

• 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