Submission #125395

#	Time	Username	Problem	Language	Result	Execution time	Memory
125395		mlyean00	Strange Device (APIO19_strange_device)	C++17	15 / 100	759 ms	17468 KiB

strange_device

#ifdef DEBUG
#define trace(x) cerr << "DEBUG: " << (#x) << " = " << (x) << endl
#else
#pragma GCC optimize("Ofast")
#define trace(x)
#endif

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;
using ll = long long;

const ll MAX = 1'000'000'000'000'000'001LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    ll A, B;
    cin >> n >> A >> B;

    ll g = gcd(A, B + 1);
    A /= g;

    ll mod;
    // Check overflow
    if (__lg(A) + __lg(B) > 62)
        mod = MAX;
    else
        mod = min(A * B, MAX);

    // The intervals to union
    vector<pair<ll, ll>> v;

    for (int i = 0; i < n; ++i) {
        ll l, r;
        cin >> l >> r;

        // Shift left endpoint such that 0 <= l < mod
        ll k = (l / mod) * mod;
        l -= k;
        r -= k;

        if (r - l + 1 >= mod) {
            v.emplace_back(0, mod - 1);
        } else if (r < mod) {
            v.emplace_back(l, r);
        } else {
            v.emplace_back(l, mod - 1);
            v.emplace_back(0, r - mod);
        }
    }

    sort(v.begin(), v.end());

    // Merge intervals
    vector<pair<ll, ll>> v_merged;
    v_merged.push_back(v.front());

    for (int i = 1; i < v.size(); ++i) {
        auto& last = v_merged.back();
        if (last.second + 1 < v[i].first) {
            v_merged.push_back(v[i]);
        } else {
            last.second = v[i].second;
        }
    }

    ll ans = 0;
    for (auto [l, r] : v_merged) {
        ans += r - l + 1;
    }

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i) {
                     ~~^~~~~~~~~~

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