Submission #934953

#	Time	Username	Problem	Language	Result	Execution time	Memory
934953		peterandvoi	Strange Device (APIO19_strange_device)	C++17	0 / 100	954 ms	148640 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, res;
long long l[N], r[N];
long long tree[16 * N], lz[16 * N];
vector<long long> rem;

void apply(int id, int l, int r, long long x) {
    lz[id] += x;
    tree[id] += x * (rem[r + 1] - rem[l]);
}

void upd(int u, int v, long long x, int id = 1, int l = 0, int r = m) {
    if (u <= l && r <= v) {
        res -= x * tree[id];
        apply(id, l, r, x);
        return;
    }
    int mid = l + r >> 1;
    if (lz[id]) {
        apply(id << 1, l, mid, lz[id]);
        apply(id << 1 | 1, mid + 1, r, lz[id]);
        lz[id] = 0;
    }
    if (u <= mid) {
        upd(u, v, x, id << 1, l, mid);
    }
    if (mid < v) {
        upd(u, v, x, id << 1 | 1, mid + 1, r);
    }
    tree[id] = tree[id << 1] + tree[id << 1 | 1];
}

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;
    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];
        res += r[i] - l[i] + 1;
        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);
        }
    }
    cout << res;
}

Compilation message (stderr)

strange_device.cpp: In function 'void upd(int, int, long long int, int, int, int)':
strange_device.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~

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