Submission #230059

#	Time	Username	Problem	Language	Result	Execution time	Memory
230059		AMO5	Strange Device (APIO19_strange_device)	C++98	100 / 100	599 ms	37460 KiB

strange_device

// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn=1e6+5;
ll const MAX=1e18+10;

ll l[mxn],r[mxn];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	ll n,a,b;
	cin >> n >> a >> b;
	ll gcd = __gcd(a,b+1); 
	ll maxi = a/gcd;
	if(__lg(a)+__lg(b)>60){
		maxi = MAX;
	}else{
		maxi = min(maxi*b,MAX);
	}
	bool all=0;
	vector<pll>seg;
	for(int i=0; i<n; i++){
		cin >> l[i] >> r[i];
		if(r[i]-l[i]+1>=maxi)all=1;
		l[i]%=maxi; r[i]%=maxi;
		if(r[i]>=l[i]){
			seg.emplace_back(pll(l[i],r[i]));
		}else{
			seg.emplace_back(pll((ll)0,r[i]));
			seg.emplace_back(pll(l[i],ll(maxi-1)));
		}
	}
	if(all){
		cout << maxi << endl;
		return 0;
	}
	sort(all(seg));
	ll ans = 0;
	ll cur = 0;
	for(int i=0; i<(int)seg.size(); i++){
		ans += max(ll(0),seg[i].se+1-max(seg[i].fi,cur));
		cur = max(seg[i].se+1,cur);
	}
	cout << ans << endl;
}	

• 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