Submission #567738

#	Time	Username	Problem	Language	Result	Execution time	Memory
567738		8e7	Strange Device (APIO19_strange_device)	C++17	100 / 100	727 ms	55100 KiB

strange_device

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T,class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll inf = 1LL<<60;
ll mul(ll a, ll b) {
	ll ret = 0;
	while (b) {
		if (a > inf) return inf;
		if (b & 1) ret += a;
		a += a;
		b >>= 1;
		if (ret > inf) return inf;
	}
	return ret;
}
int main() {
	io
	ll n, A, B;
	cin >> n >> A >> B;
	ll cy = mul(A / __gcd(A, B + 1), B);
	vector<pii> ev;
	for (int i = 0;i < n;i++) {
		ll l, r;
		cin >> l >> r;
		if (r - l + 1 >= cy) {
			cout << cy << "\n";
			return 0;
		}
		l %= cy, r %= cy;
		if (l <= r) {
			ev.push_back({l, 1});
			ev.push_back({r + 1, -1});
		} else {
			ev.push_back({l, 1});
			ev.push_back({0, 1});
			ev.push_back({r+1, -1});
		}
	}
	ev.push_back({cy, 0});
	sort(ev.begin(), ev.end());
	
	ll prv = -1, val = 0, ans = 0;
	int siz = ev.size();
	for (int i = 0;i < siz;i++) {
		int tmp = i;
		ll to = val;	
		while (tmp < siz - 1 && ev[tmp+1].ff == ev[i].ff) {
			to += ev[tmp].ss;
			tmp++;
		}
		to += ev[tmp].ss;
		if (val) ans += ev[i].ff - prv;
		val = to;
		prv = ev[i].ff;
		i = tmp;
	}
	cout << ans << "\n";	
}

• 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