Submission #935000

#	Time	Username	Problem	Language	Result	Execution time	Memory
935000		peterandvoi	Strange Device (APIO19_strange_device)	C++17	100 / 100	778 ms	102672 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = (int) 1e6 + 5;
const long long LIM = (long long) 1e18;

int n, m;
long long a, b, c;
long long l[N], r[N];
long long f[4 * N];
vector<long long> rem;

void upd(int l, int r, long long x) {
    f[l] += x;
    f[r + 1] -= x;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> a >> b;
    a /= __gcd(a, b + 1);
    if (a <= LIM / b) {
        c = a * b;
    } else {
        c = LIM + 1;
    }
    rem.emplace_back(0);
    rem.emplace_back(c);
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i];
        rem.emplace_back(l[i] % c);
        if (l[i] % c - 1 >= 0) {
            rem.emplace_back(l[i] % c - 1);
        }
        rem.emplace_back(r[i] % c);
        if (r[i] % c + 1 < c) {
            rem.emplace_back(r[i] % c + 1);
        }
    }
    sort(rem.begin(), rem.end());
    rem.erase(unique(rem.begin(), rem.end()), rem.end());
    m = (int) rem.size() - 2;
    auto get_pos = [&](long long i) {
        return lower_bound(rem.begin(), rem.end(), i) - rem.begin();
    };
    for (int i = 1; i <= n; ++i) {
        long long cnt = r[i] / c - l[i] / c;
        int L = get_pos(l[i] % c);
        int R = get_pos(r[i] % c);
        if (cnt) {
            if (R < L) {
                if (R + 1 <= L - 1) {
                    upd(R + 1, L - 1, cnt - 1);
                }
                upd(0, R, cnt);
                upd(L, m, cnt);
            } else {
                upd(L, R, cnt + 1);
                if (0 <= L - 1) {
                    upd(0, L - 1, cnt);
                }
                if (R + 1 <= m) {
                    upd(R + 1, m, cnt);
                }
            }
        } else {
            upd(L, R, 1);
        }
    }
    long long res = 0;
    for (int i = 0; i <= m; ++i) {
        if (i) {
            f[i] += f[i - 1];
        }
        res += (f[i] > 0) * (rem[i + 1] - rem[i]);
    }
    cout << res;
}

• 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