Submission #481892

#	Time	Username	Problem	Language	Result	Execution time	Memory
481892		radal	이상한 기계 (APIO19_strange_device)	C++14	100 / 100	1157 ms	100228 KiB

strange_device

#include <bits/stdc++.h>
#pragma GCC target ("avx,avx2,fma")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#define X first
#define Y second
#define debug(x) cerr << #x << ": " << x << endl;
#define endl '\n'
#define pb push_back
#define rep(i,l,r) for (int i=l; i<r; i++)
#define repr(i,r,l) for (int i=r; i>=l; i--)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const long long int N=5e2+20,mod = 1e9+7,inf=1e18;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    return a+b;
}
ll gcd(ll a,ll b){
    if (!b) return a;
    if (b < a) swap(a,b);
    return gcd(a,b%a);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n;
    ll a,b,z;
    cin >> n >> a >> b;
    a /= gcd(a,b+1);
    debug(gcd(4,6));
    if (b >= (inf+a-1)/a) z = inf+1;
    else z = a*b;
    set<pll> st;
    rep(i,0,n){
        ll l,r;
        cin >> l >> r;
        if (r-l+1 >= z){
            cout << z;
            return 0;
        }
        if (r%z < l%z){
            auto it = st.upper_bound({l%z,0});
            while(it != st.end()){
                st.erase(it);
                it = st.upper_bound({l%z,0});
            }
            st.insert({l%z,z});
            st.insert({0,r%z+1});
        }
        else{
            st.insert({l%z,r%z+1});
        }
    }
    pll p = {1,-1};
    ll ans = 0;
    for(pll q : st){
        if (q.X >= p.X && q.Y <= p.Y)
            continue;
        if (q.X <= p.Y){
            ans += q.Y-p.Y;
            p.Y = q.Y;
            continue;
        }
        p = q;
        ans += p.Y-p.X;
    }
    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