제출 #145367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145367		dolphingarlic	Strange Device (APIO19_strange_device)	C++14	35 / 100	1016 ms	68212 KiB

strange_device

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
typedef long long ll;
using namespace std;

// Observation: pairs are periodic, period = B * (A / gcd(A, B + 1))
// We can thus "line sweep" i.e. keep a vector of events and +1 for add,
// -1 for remove and count as long as positive

ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, a, b;
    cin >> n >> a >> b;
    ll period = b * (a / gcd(a, b + 1));
    vector<pair<ll, int>> events;
    FOR(i, 0, n) {
        ll x, y;
        cin >> x >> y;
        x += period - 1;
        y += period - 1;
        if (y - x >= period) {
            return cout << period << '\n', 0;
        }
        if (x % period > y % period) {
            events.push_back(make_pair(1, 0));
            events.push_back(make_pair(y % period + 1, 1));
            events.push_back(make_pair(x % period + 1, 0));
            events.push_back(make_pair(period, 1));
        } else {
            events.push_back(make_pair(x % period + 1, 0));
            events.push_back(make_pair(y % period + 1, 1));
        }
    }
    sort(events.begin(), events.end());
    ll cnt = 0, leftmost = -1, ans = 0;
    for (auto& i : events) {
        if (!i.second) {
            cnt++;
            if (leftmost == -1) leftmost = i.first;
        } else {
            cnt--;
            if (cnt == 0) {
                ans += (i.first - leftmost + 1);
                leftmost = -1;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30