Submission #983242

#	Time	Username	Problem	Language	Result	Execution time	Memory
983242		Abito	Strange Device (APIO19_strange_device)	C++17	100 / 100	477 ms	168504 KiB

strange_device

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=1e6+5;
int n,l[N],r[N],a,b;
__int128 A,B,L[N],R[N];
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>a>>b;
    a/=__gcd(a,b+1);
    A=a,B=b;
    A*=B;
    for (int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        L[i]=l[i];
        R[i]=r[i];
    }
    vector<pair<__int128,__int128>> v;
    for (int i=1;i<=n;i++){
        if (R[i]-L[i]+1>=A) v.pb({0,A-1});
        else{
            if (R[i]%A>=L[i]%A) v.pb({L[i]%A,R[i]%A});
            else{
                v.pb({L[i]%A,A-1});
                v.pb({0,R[i]%A});
            }
        }
    }
    sort(v.begin(),v.end());
    //for (auto u:v) cout<<u.F<<' '<<u.S<<endl;
    pair<__int128,__int128> cur=v[0];
    vector<pair<__int128,__int128>> f;
    for (auto u:v){
        __int128 ll=max(cur.F,u.F),rr=min(cur.S,u.S);
        if (ll>rr){
            f.pb(cur);
            cur=u;
        }
        else{
            ll=min(cur.F,u.F);
            rr=max(cur.S,u.S);
            cur={ll,rr};
        }
    }
    f.pb(cur);
    int ans=0;
    for (auto u:f){
        __int128 len=u.S-u.F+1;
        ans+=(int)len;
    }cout<<ans<<endl;
    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