Submission #1200102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200102		adiyer	Strange Device (APIO19_strange_device)	C++20	100 / 100	304 ms	32760 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 11;

ll n, a, b, c, res;
ll l[N], r[N];

__int128 val;

vector < pair < ll, ll > > seg;

void solve(){
    cin >> n >> a >> b;
    for(ll i = 1; i <= n; i++) cin >> l[i] >> r[i]; 
    val = a / __gcd(a, b + 1), val *= b;
    if(val > 1e18){
        for(ll i = 1; i <= n; i++) res += r[i] - l[i] + 1;
        cout << res;
        return;
    }
    c = val;
    for(ll i = 1; i <= n; i++){
        if(r[i] - l[i] + 1 >= c){ cout << c << '\n'; return; }
        l[i] %= c, r[i] %= c;
        if(l[i] <= r[i]) seg.push_back({l[i], r[i]});
        else seg.push_back({l[i], c - 1}), seg.push_back({0, r[i]});
    }
    sort(seg.begin(), seg.end());
    ll mx = -1;
    for(auto [l, r] : seg){
        if(r > mx){
            res += r - max(l - 1, mx);
            mx = r;
        }
    }
    cout << res;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
}

• 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