Submission #361964

#	Time	Username	Problem	Language	Result	Execution time	Memory
361964		bigDuck	Strange Device (APIO19_strange_device)	C++14	100 / 100	748 ms	67292 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int n, a, b;

int gcd(int x, int y){
    int a=x, b=y;
    if(a<b){
        swap(a, b);
    }
    if(b==0){return a;}
    return gcd(b, a%b);
}



int32_t main(){
INIT
cin>>n>>a>>b;
int k=a/gcd(a, b+1);
int m=0;
if( (( ((ll)(1e9))*((ll)(1e9)) )/(b))>=(k) ){
    m=k*(b);
}
else{
    m=((ll)2*((ll)(1e9))*((ll)(1e9)));
}
//cout<<(m)<<"\n";
set<pii> s;
int l, r;
for(int i=1; i<=n; i++){
    cin>>l>>r;
    s.insert( {(l%m), min(m-1, (l%m)+r-l )} );
    if( (r-l+1)>=m ){
        cout<<m<<"\n";
        return 0;
    }
    if( r>(l+(m-1-l%m) ) ){
        s.insert({0, r%m});
    }
}
l=0, r=-1;
int res=0;
for(auto it=s.begin(); it!=s.end(); it++){
    //cout<<l<<" "<<r<<"\n";
    if(r==-1){
        r=it->sc; l=it->ft;
        continue;
    }
    if(it->ft>r){
        res+=(r-l+1);
        l=it->ft, r=it->sc;
        continue;
    }
    r=max(r, it->sc);
}
//cout<<l<<" "<<r<<"\n";
res+=(r-l+1);
cout<<res;

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