Submission #1262944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262944		kamrad	Strange Device (APIO19_strange_device)	C++20	100 / 100	953 ms	110064 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll = __int128;
using pll = pair<ll, ll>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define rand(l, r)        uniform_ll_distribution<ll64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const ll Mod    = 1e9 + 7; //998244353;
const ll LG     = 64;
const ll SQ     = 500;
const ll Inf    = 2e9 + 10;

ll n, A, B;
vector <ll> pts;

ll GCD(ll x, ll y) {
	if(x < y) swap(x, y);
	if(!y) return x;
	return GCD(y, x%y);
}

ll LCP(ll x, ll y) {
	return x*y/GCD(x, y);
}

map <ll, int> val;

void print(ll x) {
	vector <int> ret;
	if(x == 0)
		cout << 0;
	while(x) {
		ret.pb(x%10);
		x /= 10;
	}
	reverse(all(ret));
	for(auto i : ret)
		cout << i;
}

int main() {
	IOS;

	long long in1, in2, in3;
	cin >> in1 >> in2 >> in3;
	n = in1;
	A = in2;
	B = in3;
	ll len = (LCP(A, B+1)/(B+1))*B;
	
	pts.pb(0);
	pts.pb(len-1);
	pts.pb(len);
	for(ll i = 1; i <= n; i++) {
		long long in1, in2;
		ll l, r;
		
		cin >> in1 >> in2;
		l = in1;
		r = in2;

		if(r-l+1 >= len) {
			print(len);
			return 0;
		}

		if(l%len <= r%len) {
			val[l%len]++;
			val[r%len + 1]--;
			pts.pb(l%len);
			pts.pb(r%len + 1);
		}
		else {
			val[l%len]++;
			val[len]--;
			pts.pb(l%len);
			val[0]++;
			val[r%len + 1]--;
			pts.pb(r%len + 1);
		}
	}

	sort(all(pts));
	pts.resize(unique(all(pts))-pts.begin());
	
	ll cur = 0;
	ll ans = 0;
	for(ll i = 0; i < sz(pts); i++) {
		ll x = pts[i];
		cur += val[x];
		if(cur > 0 and i < sz(pts)-1)
			ans += pts[i+1]-pts[i];
	}

	print(ans);
}

• 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