Submission #448187

#	Time	Username	Problem	Language	Result	Execution time	Memory
448187		Vladithur	Strange Device (APIO19_strange_device)	C++17	5 / 100	688 ms	524292 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 a, b;
	cin >> a >> b;
	
	ll tn = a * b;
	vector<ll> p(tn + 1);
	vector<bool> good(tn);
	while (n--) {
		ll l, r;
		cin >> l >> r;
		
		if (r - l + 1 >= tn) {
			p[0]++;
		} else {
			l %= tn;
			r %= tn;
			if (l <= r) {
				p[l]++;
				p[r + 1]--;
			} else {
				p[0]++;
				p[r + 1]--;
				p[l]++;
			}
		}
	}
	
	for (int i = 0; i < tn; i++) {
		p[i + 1] += p[i];
		good[i] = (p[i] > 0);
	}
	
	set<pair<ll, ll>> ts;
	for (ll x = 0; x < tn; x++) {
		if (good[x]) {
			ts.emplace((x + x / b) % a, x % b);
		}
	}
	cout << gsize(ts) << 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: 0 / 10
• Subtask 2: 0 / 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