Submission #419434

#	Time	Username	Problem	Language	Result	Execution time	Memory
419434		alireza_kaviani	Strange Device (APIO19_strange_device)	C++11	100 / 100	666 ms	69760 KiB

strange_device

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 2e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , A , B , sum , ans , L[MAXN] , R[MAXN];
vector<pll> vec;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> A >> B;
	A /= __gcd(A , B + 1);
	for(int i = 0 ; i < n ; i++){
		cin >> L[i] >> R[i];
		sum += R[i] - L[i] + 1;
	}
	if(INF / A <= B)	return cout << sum << endl , 0;
	A *= B; //cout << A << endl;
	for(int i = 0 ; i < n ; i++){
		if(R[i] - L[i] + 1 >= A)	return cout << A << endl , 0;
		L[i] %= A; R[i] %= A;
		if(L[i] <= R[i])	vec.push_back({L[i] , R[i]});
		else{
			vec.push_back({0 , R[i]});
			vec.push_back({L[i] , A - 1});
		}
	}
	sort(all(vec));
	ll l = 0 , r = -1;
	for(pll i : vec){
		if(r < i.X){
			ans += r - l + 1;
			l = INF , r = -1;
		}
		l = min(l , i.X);
		r = max(r , i.Y);
	}
	cout << ans + r - l + 1 << endl;

    return 0;
}
/*

*/

• 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