Submission #545798

#	Time	Username	Problem	Language	Result	Execution time	Memory
545798		amunduzbaev	Strange Device (APIO19_strange_device)	C++17	100 / 100	528 ms	53424 KiB

strange_device

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

#define ar array
#define int long long

/*

3 5 12
0 23
60 60
81 83

*/

const long long inf = 1e18 + 5;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, A, B; cin>>n>>A>>B;
	int cyc = A / __gcd(A, B + 1);
	if(cyc > inf / B) cyc = inf;
	else cyc *= B;
	
	vector<ar<int, 2>> tt;
	for(int i=0;i<n;i++){
		int l, r; cin>>l>>r;
		if(r - l + 1 >= cyc){
			cout<<cyc<<"\n";
			return 0;
		}
		
		l %= cyc, r %= cyc;
		if(l <= r){
			tt.push_back({l, r});
		} else {
			tt.push_back({l, cyc - 1});
			tt.push_back({0, r});
		}
	}
	
	sort(tt.begin(), tt.end());
	int res = 0, r = -1;
	for(auto x : tt){
		if(r < x[0]){
			res += (x[1] - x[0] + 1);
		} else if(r < x[1]){
			res += (x[1] - r);
		} r = max(r, x[1]);
	}
	
	cout<<res<<"\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