Submission #1044949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044949		Kel_Mahmut	Strange Device (APIO19_strange_device)	C++14	25 / 100	1223 ms	141272 KiB

strange_device

#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

ll ggcd(ll a, ll b){
	if(b == 0) return a;
	return ggcd(b, a % b);
}

const ll inf = ll(1e18) + 1;

int main(){
	ll n, a, b;
	cin >> n >> a >> b;
	vector<pair<ll, ll>> v(n);
	ll mx = 0;
	for(int i = 0; i < n; i++){
		ll l, r;
		cin >> l >> r;
		v[i] = {l, r};
		mx = max(mx, r);
	}

	ll g = ggcd(a, b + 1);
	ll sade = a / g;
	ll mod;
	if(double(sade) * double(b) >= double(inf)){
		mod = inf;
	}
	else mod = sade * b;

	set<pair<ll, int>> s;
	s.insert({-1, 1});
	s.insert({mod, 0});
	function<void(ll, ll)> add = [&](ll ql, ll qr){
		// cout << ql << ' ' << qr << endl;
		auto ileri = s.lower_bound({ql, 0});
		auto geri = prev(ileri);
		if(ileri->second == 0){
			if(qr >= ileri->first)
				s.erase(ileri);
			s.insert({ql, 0});
		}

		ileri = s.lower_bound({qr, 0});
		geri = prev(ileri);
		if(ileri->second == 0){
			if(geri->second == 1 && ql <= geri->first)
				s.erase(geri);
			s.insert({qr, 1});
		}
		// for(auto [x, y] : s){
		// 	// if(x == -1 || x == mod) continue;
		// 	// if(y == 0)
		// 	// 	ans -= x;
		// 	// else
		// 	// 	ans += x + 1;
		// 	cout << x << ' ' << y << endl;
		// } cout << endl;
	};
	for(int i = 0; i < n; i++){
		ll tl = v[i].first;
		ll tr = v[i].second;
		if(tr - tl + 1 >= mod){
			cout << mod << endl;
			exit(0);
		}
		ll sub = v[i].first / mod;
		tl -= sub * mod;
		tr -= sub * mod;
		if(tr < mod){
			add(tl, tr);
		}
		else{
			add(tl, mod - 1);
			add(0, tr - mod);
		}
	}

	ll ans = 0;

	for(auto [x, y] : s){
		if(x == -1 || x == mod) continue;
		if(y == 0)
			ans -= x;
		else
			ans += x + 1;
		// cout << x << ' ' << y << endl;
	}

	cout << ans << endl;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:85:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |  for(auto [x, y] : s){
      |           ^

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