Submission #821794

#	Time	Username	Problem	Language	Result	Execution time	Memory
821794		hngwlog	Strange Device (APIO19_strange_device)	C++14	100 / 100	656 ms	68964 KiB

strange_device

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

#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

const long long inf = 1e18;

int main() {
    fastio;

    int n;
    long long a, b;
    cin >> n >> a >> b;
    long long k = a / __gcd(b + 1, a);
    vector<pair<long long, int>> g;
    long long p = 0;
    if (inf / k < b) p = inf + 5;
    else p = k * b;
    REP(i, n) {
        long long l, r;
        cin >> l >> r;
        if (r - l + 1 >= p) {
            cout << p << '\n';
            return 0;
        }
        long long lo = l % p, hi = r % p;
        if (lo <= hi) g.push_back({lo, + 1}), g.push_back({hi, - 1});
        else {
            g.push_back({lo, + 1}), g.push_back({p - 1, - 1});
            g.push_back({0, + 1}), g.push_back({hi, - 1});
        }
    }
    sort(g.begin(), g.end(), [&] (const pair<long long, int> a, pair<long long, int> b) { return (a.fi != b.fi) ? (a.fi < b.fi) : (a.se > b.se); });
    int i = 0, sum = 0;
    long long ans = 0, cur;
    while (i < _size(g)) {
        int cur_sum = sum;
        int j = i;
        while (j < _size(g) && g[j].fi == g[i].fi && g[j].se == + 1) sum++, j++;
        if (!cur_sum && sum) ans++;
        else if (sum) ans += g[i].fi - cur;
        while (j < _size(g) && g[j].fi == g[i].fi) sum--, j++;
        cur = g[i].fi;
        i = j;
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:52:38: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |         else if (sum) ans += g[i].fi - cur;

• 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