Submission #401786

#	Time	Username	Problem	Language	Result	Execution time	Memory
401786		AmineTrabelsi	Strange Device (APIO19_strange_device)	C++14	100 / 100	588 ms	32884 KiB

strange_device

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

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    long long a,b;
    cin>>n>>a>>b;
    a /= __gcd(a,b+1);
    long long max_ans = 1000000000000000001;
    long long mod = max_ans;
    if (a <= LLONG_MAX / b)mod = a*b;
    vector<pair<long long,long long>> q;
    for(int i=0;i<n;i++){
        long long l,r;
        cin>>l>>r;
        if(r-l+1 >= mod){
            cout << mod << '\n';
            return 0;
        }
        long long ll = l% mod, rr = r% mod;
        if(ll  <= rr){
            q.push_back({ll,rr});
        }else {
            q.push_back({0,rr});
            q.push_back({ll,mod-1});
        }
    }
    sort(q.begin(),q.end());
    long long ans = 0,curr_l = q[0].first,curr_r = q[0].second;
    for(auto p:q){
        if(p.first<= curr_r){
            curr_r = max(curr_r,p.second);
        }else{
            ans += curr_r-curr_l+1;
            curr_l = p.first;
            curr_r = p.second;
        }
    }
    ans += curr_r-curr_l+1;
    cout << ans << '\n';
    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