Submission #409666

#	Time	Username	Problem	Language	Result	Execution time	Memory
409666		glebustim	Strange Device (APIO19_strange_device)	C++17	100 / 100	930 ms	98048 KiB

strange_device

#include <bits/stdc++.h>
typedef long long ll;
typedef __int128 lll;
using namespace std;

lll gcd(lll x, lll y) {
    while (y > 0) {
        lll z = x % y;
        x = y;
        y = z;
    }
    return x;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll _a, _b;
    cin >> n >> _a >> _b;
    lll a = _a, b = _b, len = a * b / gcd(a, b + 1);
    map<lll, int> s;
    for (int i = 0; i < n; ++i) {
        ll l, r;
        cin >> l >> r;
        lll f = l % len;
        if (f + r - l >= len) {
            ++s[0];
            --s[r % len + 1];
            ++s[f];
            --s[len];
        }
        else {
            ++s[f];
            --s[f + r - l + 1];
        }
    }
    int bal = 0;
    ll ans = 0;
    lll prev = -1;
    for (auto [t, e]: s) {
        if (bal > 0)
            ans += t - prev;
        bal += e;
        prev = t;
    }
    cout << ans << endl;
}

• 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