Submission #1358027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1358027		eliminator_101	Strange Device (APIO19_strange_device)	C++20	35 / 100	262 ms	32588 KiB

strange_device

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

#define int long long
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,a,b;
    cin>>n>>a>>b;
    vector<pair<int,int>>v(n);
    for(auto&[c,d]:v){
        cin>>c>>d;
    }
    int g = __gcd(a,b+1);
    __int128 tt = a/g*b;

    int mx = -1,ans=0;
    vector<pair<int,int>>v1;
    if(tt<=(__int128)1e18){
        for (auto[c,d]:v){
            if(d-c>tt){
                ans=tt;
                break;
            }
            int c1 = c%((int)tt);
            int d1 = d%((int)tt);
            if(c1>d1){
                v1.push_back({c1,tt-1});
                v1.push_back({0LL,d1});
            }else{
                v1.push_back({c1,d1});
            }
        }
    }
    if(ans){
        cout<<ans<<endl;
        return 0;
    }
    sort(v1.begin(), v1.end());
    for (auto[c,d]:v1){
        if (c>mx){
            ans+=d-c+1;
            mx=d;
        }else if(d>mx){ 
            ans+=d-mx;
            mx=d;
        }
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30