Submission #1085659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085659		4QT0R	Strange Device (APIO19_strange_device)	C++17	100 / 100	445 ms	116048 KiB

strange_device

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

void fastscan(ll &n){
	n=0;
	for(char zn=getchar();47<zn && zn<58; zn=getchar()){
		n=10*n+zn-48;
	}
}

set<pair<ll,ll>> s;

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

	ll n,A,B;
	fastscan(n);
	fastscan(A);
	fastscan(B);
	A/=gcd((long long)A,(long long)(B+1));
	ll mod=A*B;
	for (ll i = 1; i<=n; i++){
		ll l,p;
		fastscan(l);
		fastscan(p);
		if (l/mod!=p/mod){
			s.insert({l%mod,mod-1});
			s.insert({0,p%mod});
		}
		else s.insert({l%mod,p%mod});
	}
	ll mx=-1;
	ll ans=0;
	for (auto [l,p] : s){
		if (p<=mx)continue;
		ans+=p-max(mx+1,l)+1;
		mx=max(mx,p);
	}
	cout << (long long)ans << '\n';
}

• 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