oj.uz

Submission #934953

# Submission time Handle Problem Language Result Execution time Memory
934953 2024-02-28T09:11:24 Z peterandvoi Strange Device (APIO19_strange_device) C++17
0 / 100
 954 ms 148640 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 9 ms 11996 KB Output is correct
3 Correct 9 ms 9964 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 2 ms 4572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 786 ms 118388 KB Output is correct
3 Incorrect 882 ms 146540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 786 ms 118388 KB Output is correct
3 Incorrect 882 ms 146540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 786 ms 118388 KB Output is correct
3 Incorrect 882 ms 146540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4652 KB Output is correct
2 Correct 87 ms 25804 KB Output is correct
3 Correct 98 ms 24932 KB Output is correct
4 Correct 938 ms 146716 KB Output is correct
5 Correct 87 ms 25020 KB Output is correct
6 Correct 87 ms 24860 KB Output is correct
7 Correct 87 ms 25644 KB Output is correct
8 Correct 88 ms 24920 KB Output is correct
9 Correct 102 ms 24928 KB Output is correct
10 Correct 107 ms 25048 KB Output is correct
11 Correct 88 ms 25280 KB Output is correct
12 Correct 65 ms 24932 KB Output is correct
13 Correct 96 ms 24768 KB Output is correct
14 Correct 954 ms 148640 KB Output is correct
15 Incorrect 89 ms 25796 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 9 ms 11996 KB Output is correct
3 Correct 9 ms 9964 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -