Submission #729962

#	Time	Username	Problem	Language	Result	Execution time	Memory
729962		MtSaka	Strange Device (APIO19_strange_device)	C++17	100 / 100	670 ms	69004 KiB

strange_device

#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)a;++i)
#define rep3(i,a,b) for(ll i=a;i<(ll)b;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define lb(v,x) lower_bound(all(v),x);
#define ub(v,x) upper_bound(all(v),x);
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    ll a,b;cin>>a>>b;
    ll g=gcd(a,b+1);
    if((ld)(1e18)/(ld)b<a/g){
        ll ans=0;
        rep(i,n){
            ll l,r;cin>>l>>r;
            ans+=r-l+1;
        }
        cout<<ans<<endl;return 0;
    }
    vector<pair<ll,ll>>v;
    ll md=a/g*b;
    rep(i,n){
        ll l,r;cin>>l>>r;
        if(r-l+1>=md){
            cout<<md<<endl;return 0;
        }
        l%=md,r%=md;
        if(l>r){
            v.emplace_back(l,1);
            v.emplace_back(md,-1);
            v.emplace_back(0,1);
            v.emplace_back(r+1,-1);
        }
        else{
            v.emplace_back(l,1);
            v.emplace_back(r+1,-1);
        }
    }
    sort(all(v));
    ll ans=0,cnt=1;
    rep(i,1,v.size()){
        if(cnt>0){
            ans+=v[i].first-v[i-1].first;
        }
        cnt+=v[i].second;
    }
    cout<<ans<<endl;
}

• 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