Submission #768473

#	Time	Username	Problem	Language	Result	Execution time	Memory
768473		pandapythoner	Strange Device (APIO19_strange_device)	C++14	100 / 100	572 ms	68724 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define lll __int128_t
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

lll gcd(lll a, lll b) {
    while (a != 0) {
        b %= a;
        swap(a, b);
    }
    return b;
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int n;
    ll A, B;
    cin >> n >> A >> B;
    lll t = (lll)(B) * (A / gcd(A, B + 1));
    vector<pair<ll, int>> f;
    f.reserve(n * 4);
    for (int i = 0; i < n; i += 1) {
        ll l, r;
        cin >> l >> r;
        r += 1;
        if (r - l >= t) {
            f.push_back(make_pair(0, 1));
            f.push_back(make_pair(t, -1));
            continue;
        }
        ll nl = l % t;
        ll nr = r % t;
        if (nl < nr) {
            f.push_back(make_pair(nl, 1));
            f.push_back(make_pair(nr, -1));
            continue;
        }
        f.push_back(make_pair(nl, 1));
        f.push_back(make_pair(t, -1));
        f.push_back(make_pair(0, 1));
        f.push_back(make_pair(nr, -1));
    }
    sort(all(f));
    ll count = 0;
    ll biba = 0;
    for (int i = 0; i + 1 < (int)f.size(); i += 1) {
        biba += f[i].second;
        if (biba > 0) {
            count += f[i + 1].first - f[i].first;
        }
    }
    cout << count << "\n";
    /*
    vector<ll> usd(t, 0);
    for (int i = 0; i < n; i += 1) {
        ll l, r;
        cin >> l >> r;
        for (int j = l; j <= r; j += 1) {
            usd[j % t] = 1;
        }
    }
    ll count = 0;
    for (int j = 0; j < t; j += 1) {
        count += usd[j];
    }
    cout << count << "\n";
    */
    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