Submission #252810

#	Time	Username	Problem	Language	Result	Execution time	Memory
252810		orgiooo	Strange Device (APIO19_strange_device)	C++14	100 / 100	2542 ms	106452 KiB

strange_device

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ret return 0
#define con continue
#define db double
#define gcd __gcd
#define freopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
using namespace std;
ll n,m,ans,cnt,x,y,z,u;
ll i,j,r,l,k;
ll a[1234567],b[1234567],d[1234567],e[1234567];
map <ll,ll> f;
set<pair<ll,ll>> s;
set<int>::iterator it;
vector <ll> c[1234567];
string p,q,w;
ll lcm(ll x,ll y){
    ll z=gcd(x,y);
    return x*y/z;
}
int main(){
    ll A,B;
    cin>>n>>A>>B;
    z=A/__gcd(A,B+1);
    if (z>1e18/B){
        z=1000000000000000001;
    }else{
        z*=B;
    }
    while (n--){
        cin>>l>>r;
        if (r-l+1>=z){
            cout<<z;
            ret;
        }
        l%=z;
        r%=z;
        if (l<=r){
            s.insert({l,r});
        }else {
            s.insert({0,r});
            s.insert({l,z-1});
        }
    }
    ll mm=-1;
    while (s.size()!=0){
        auto t=*s.begin();
        s.erase(*s.begin());
        x=t.first;
        y=t.second;
        mm=max(mm,x-1);
        ans+=max(y-mm,0ll);
        mm=max(y,mm);
    }
    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