Submission #448192

#	Time	Username	Problem	Language	Result	Execution time	Memory
448192		Vladithur	Strange Device (APIO19_strange_device)	C++17	100 / 100	952 ms	78796 KiB

strange_device

//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")
//#include <x86intrin.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define PI 3.141592653589793L
#define FAST ios::sync_with_stdio(false); cin.tie(NULL);
// Use for file I/O;
#define FIN string _fname = "input"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

#define FIN2 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define RINIT mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

using namespace std;
//using namespace __gnu_pbds;
//typedef gp_hash_table<int, int, hash<int>> ht;

const char nl = '\n';

typedef long long ll;
typedef long double ld;
// typedef unsigned int uint;
typedef unsigned long long ull;

const ll inf = 1e9 + 10;
const ll inf2 = 1e18 + 99LL;
const ld inf3 = 1e17;
const ll mod = 1e9+7, mod2 = 998244353;
const ld eps = 1e-9;
const bool local = false;

//RINIT;
const int logn = 21, maxn = 1000000, maxm = 100000, maxn2 = 3;	

int main() {
	FAST;
	
	int n;
	cin >> n;
	ll ta, tb;
	cin >> ta >> tb;
	ll g = gcd(ta, tb + 1);
	//auto g = gcd(ta, tb);
	//ta /= g; tb /= g;
	//cout << ta << ' ' << tb << ' ' << tn << nl;
	__int128 a = ta / g, b = tb;
	__int128 tn = a * b;
	
	vector<pair<__int128, ll>> segs;
	while (n--) {
		ll l, r;
		cin >> l >> r;
		
		if (r - l + 1 >= tn) {
			segs.emplace_back(0, 1);
			segs.emplace_back(tn, -1);
		} else {
			l %= tn;
			r %= tn;
			if (l <= r) {
				segs.emplace_back(l, 1);
				segs.emplace_back(r + 1, -1);
			} else {
				segs.emplace_back(0, 1);
				segs.emplace_back(r + 1, -1);
				segs.emplace_back(l, 1);
				segs.emplace_back(tn, -1);
			}
		}
	}
	
	sort(all(segs));
	__int128 ans = 0, ti = 0, px = -1, ct = 0;
	while (ti < gsize(segs)) {
		__int128 tx = segs[ti].first;
		if (ct) ans += tx - px;
		px = tx;
		while (ti < gsize(segs) && segs[ti].first == tx) {
			ct += segs[ti].second;
			ti++;
		}
	}
	
	cout << (ll)ans << nl;
}

// © Benq 
/* stuff you should look for
	* int overflow, array bounds	
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

• 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