Submission #714926

#	Time	Username	Problem	Language	Result	Execution time	Memory
714926		MISM06	Strange Device (APIO19_strange_device)	C++14	20 / 100	1815 ms	70600 KiB

strange_device

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;

set < plll > s;

plll find (int id) {
	auto it = s.lower_bound({id + 1ll, {0, 0}});
	it = prev(it);
	return *it;
}

void add (ll l, ll r) {
	plll x = find(l);
	if (x.F < l) {
		s.erase(x);
		s.insert({x.F, {l - 1ll, x.S.S}});
		s.insert({l, x.S});
	}
	x = find(r);
	if (x.S.F > r) {
		s.erase(x);
		s.insert({x.F, {r, x.S.S}});
		s.insert({r + 1ll, x.S});
	}
	x = *s.lower_bound({l, {0, 0}});
	while (x.F <= r) {
		s.erase(x);
		if (x.S.F == r) break;
		x = *s.lower_bound({l, {0, 0}});
	}
	s.insert({l, {r, 1}});
}

void solve () {

	int n;
	ll A, B;
	cin >> n >> A >> B;
	dl a = A, b = (B + 1ll);
	dl x = __gcd(A, B + 1ll);
	dl lcm = (a * b) / x;
	dl y = lcm / b;
	dl bb = B;
	dl z = y * bb;
	ll t;
	if (z > 1e18) t = 1e8;
	else t = z;
	s.insert({0, {t - 1ll, 0}});
	s.insert({inf, {inf, inf}});
	s.insert({-1, {-1, -1}});
	bool ch = 0;
	ll en = t - 1ll;
	for (int i = 1; i <= n; i++) {
		ll l, r; cin >> l >> r;
		ll len = (r - l + 1ll);
		if (len >= t) {
			ch = 1;
			add(0, en);
		}
		if (ch) continue;
		l = l % t;
		r = r % t;
		if (l <= r) add(l, r);
		else {
			add(l, en);
			add(0, r);
		}
	}
	ll ans = 0;
	for (auto it = s.begin(); it != s.end(); ++it) {
		plll x = *it;
		if (x.S.S == 1) ans += (x.S.F - x.F + 1ll);
	}
	cout << ans << '\n';
}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	

	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//inhonorofsbi;

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30