Submission #1158261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158261		AlgorithmWarrior	Strange Device (APIO19_strange_device)	C++20	100 / 100	1086 ms	63120 KiB

strange_device

#include <bits/stdc++.h>
#define ll __int128

using namespace std;

int const MAX=4e6+5;
struct operation{
    ll pos;
    int type;
    bool operator<(operation ot){
        return pos<ot.pos;
    }
}ops[MAX];

ll cmmdc(ll a,ll b){
    while(b){
        ll r=a%b;
        a=b;
        b=r;
    }
    return a;
}

ll cmmmc(ll a,ll b){
    return a*b/cmmdc(a,b);
}

long long n,a,b;
ll rep;
int total_ops;

bool create_ops(){
    bool all=0;
    int i;
    for(i=1;i<=n;++i){
        long long l,r;
        cin>>l>>r;
        if(r-l+1>=rep)
            all=1;
        else{
            ll rest1=l%rep;
            ll rest2=r%rep;
            if(rest1<=rest2){
                ops[++total_ops]={rest1,1};
                ops[++total_ops]={rest2+1,-1};
            }
            else{
                ops[++total_ops]={rest1,1};
                ops[++total_ops]={rep,-1};
                ops[++total_ops]={0,1};
                ops[++total_ops]={rest2+1,-1};
            }
        }
    }
    sort(ops+1,ops+total_ops+1);
    return all;
}

ll solve(){
    ll total=0;
    int sum=0;
    int i;
    for(i=1;i<=total_ops;++i){
        if(sum>0)
            total+=ops[i].pos-ops[i-1].pos;
        sum+=ops[i].type;
    }
    return total;
}

int main()
{
    cin>>n>>a>>b;
    rep=cmmmc(a,b+1)/(b+1)*b;
    if(create_ops())
        cout<<(long long)rep;
    else
        cout<<(long long)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