Submission #1347785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347785		goodpjw2008	Strange Device (APIO19_strange_device)	C++20	100 / 100	304 ms	16984 KiB

strange_device

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
using pii = pair<int,int>;
using i128 = __int128;
using pii = pair<int,int>;
vector<pii>v;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,a,b,mod,x,y;
    cin>>n>>a>>b;
    i128 temp=(i128)a/__gcd(a,b+1)*b;
    if(temp>1e18){
        mod=1e18+1;
    }
    else mod=temp;
    for(int i = 0; i < n; i++){
        cin>>x>>y;
        if(y-x>=mod){
            cout<<mod;
            return 0;
        }
        if(x%mod>y%mod){
            v.push_back({x%mod,mod-1});
            v.push_back({0,y%mod});
        }
        else v.push_back({x%mod,y%mod});
    }
    sort(v.begin(),v.end());
    int s=-1,e=-2,ans=0;
    for(auto &[x,y]:v){
        if(x<=e){
            if(y>e)e=y;
        }
        else{
            ans+=e-s+1;
            s=x,e=y;
        }
    }
    ans+=e-s+1;
    cout<<ans;
}

• 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