Submission #516269

#	Time	Username	Problem	Language	Result	Execution time	Memory
516269		jk410	Strange Device (APIO19_strange_device)	C++17	100 / 100	685 ms	86232 KiB

strange_device

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct gugan{
    ll l,r;
};
struct q{
    ll t;
    int v;
    bool operator<(const q &tmp)const{
        return t<tmp.t;
    }
};
int N;
ll A,B,T,Ans;
gugan G[1000001];
vector<q> V;
void f(ll l,ll r){
    V.push_back({l,1});
    V.push_back({r+1,-1});
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>A>>B;
    if (log10(A/__gcd(A,B+1))+log10(B)>18)
        T=1e18+1;
    else
        T=A/__gcd(A,B+1)*B;
    for (int i=1; i<=N; i++){
        cin>>G[i].l>>G[i].r;
        if (G[i].r-G[i].l+1>=T){
            cout<<T;
            return 0;
        }
    }
    for (int i=1; i<=N; i++){
        G[i].l%=T;
        G[i].r%=T;
        if (G[i].l>G[i].r){
            f(0,G[i].r);
            f(G[i].l,T-1);
        }
        else
            f(G[i].l,G[i].r);
    }
    sort(all(V));
    for (int i=0,j,v=0,tmp; i<(int)V.size();){
        if (!v)
            tmp=i;
        for (j=i; j<(int)V.size()&&V[j].t==V[i].t; j++)
            v+=V[j].v;
        if (!v)
            Ans+=V[i].t-V[tmp].t;
        i=j;
    }
    cout<<Ans;
    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