Submission #1198165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198165		hengliao	Strange Device (APIO19_strange_device)	C++20	100 / 100	308 ms	32700 KiB

strange_device

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;
typedef __int128 i128;

const ll inf=1e18+5;

void solve(){
    ll n, a, b;
    cin>>n>>a>>b;
    vector<pll> v(n);
    for(auto &[x, y]:v){
        cin>>x>>y;
    }
    ll tep=(b%a+1)%a;
    i128 mod;
    if(tep==0){
        mod=b;
    }
    else{
        mod=a/__gcd(a, tep);
        mod*=b;
    }
    if(mod>(i128) inf){
        ll ans=0;
        for(auto &[x, y]:v){
            ans+=y-x+1;
        }
        cout<<ans<<'\n';
        return;
    }
    vector<pll> dumb;
    for(auto &[x, y]:v){
        if(y-x+1>=mod){
            cout<<(ll) mod<<'\n';
            return;
        }
        ll f=x%mod;
        ll s=y%mod;
        if(f>s){
            dumb.pb({f, mod-1});
            dumb.pb({0, s});
        }
        else{
            dumb.pb({f, s});
        }
    }
    sort(dumb.begin(), dumb.end());
    ll ans=0;
    ll mx=-1;
    for(auto &[x, y]:dumb){
        if(y>mx){
            ans+=min(y-x+1, y-mx);
            mx=y;
        }
    }
    cout<<ans<<'\n';
}

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

  solve();

  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