Submission #391267

#	Time	Username	Problem	Language	Result	Execution time	Memory
391267		phathnv	이상한 기계 (APIO19_strange_device)	C++11	100 / 100	828 ms	69116 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
ll a, b;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> a >> b;

    ll k = a / __gcd(a, b + 1);
    ll cycle = 0;
    if (b > 2e18 / k)
        cycle = 2e18;
    else
        cycle = b * k;

    vector<pair<ll, int>> e;
    auto addSegment = [&](ll l, ll r){
        e.push_back({l, 1});
        e.push_back({r + 1, -1});
    };
    for(int i = 1; i <= n; i++){
        ll l, r;
        cin >> l >> r;
        if (r - l + 1 >= cycle){
            cout << cycle;
            return 0;
        }
        l %= cycle;
        r %= cycle;
        if (l <= r){
            addSegment(l, r);
        } else {
            addSegment(l, cycle - 1);
            addSegment(0, r);
        }
    }
    sort(e.begin(), e.end());
    int cnt = 0;
    ll res = 0, last = 0;
    for(auto p : e){
        if (p.first != last){
            res += (cnt > 0) * (p.first - last);
            last = p.first;
        }
        cnt += p.second;
    }
    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