oj.uz

Submission #120505

# Submission time Handle Problem Language Result Execution time Memory
120505 2019-06-24T17:17:43 Z model_code Strange Device (APIO19_strange_device) C++17
35 / 100
 2244 ms 183064 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define m_p make_pair
using namespace std;

typedef long long ll;

const ll llinf = 1e18;

const int maxn = 4e6 + 100, inf = 1e9 + 100;

pair<pair<ll, bool>, ll> mas[2 * maxn];

pair<ll, ll> arr[maxn];

pair<ll, ll> seg[maxn];

bool arr_all;

int szmas, szarr, szseg, szind;

ll y;

ll ind[maxn];

int val[maxn];

bool good[maxn];

void add_mas(ll l, ll r, ll w) {
    mas[szmas++] = {{l, 0}, w};
    mas[szmas++] = {{r + 1, 1}, w};
    ind[szind++] = w;
}

void add_arr(ll l, ll r) {
    arr[szarr++] = {l, r};
}

ll cur;

void add_seg(ll l, ll r) {
    seg[szseg++] = {l, r};
    cur += r - l + 1;
}

int get_ind(ll w) {
    return lower_bound(ind, ind + szind, w) - ind;
}

void add(ll w) {
    int id = get_ind(w);
    if (good[id])
        return;
    if (val[id] == 0)
        cur++;
    val[id]++;
}

void rem(ll w) {
    int id = get_ind(w);
    if (good[id])
        return;
    val[id]--;
    if (val[id] == 0)
        cur--;
}

int main() {
    #ifdef ONPC
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll x;
    cin >> n >> x >> y;
    x /= __gcd(x, y + 1);
    for (int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        if (r - l < y && l % y <= r % y)
            add_mas(l % y, r % y, (l / y) % x);
        else {
            if (l % y != 0)
                add_mas(l % y, y - 1, (l / y) % x), l += y - l % y;
            if (r % y != y - 1)
                add_mas(0, r % y, (r / y) % x), r -= r % y + 1;
            if (l > r)
                continue;
            l /= y;
            r /= y;
            if (r - l + 1 >= x)
                arr_all = 1;
            else
                if (l % x <= r % x)
                    add_arr(l % x, r % x);
                else
                    add_arr(l % x, x - 1), add_arr(0, r % x);
        }
    }
    if (arr_all) {
        add_seg(0, x - 1);
    } else {
        sort(arr, arr + szarr);
        ll L = -1, R = -1;
        for (int i = 0; i < szarr; i++) {
            if (L == -1 || R + 1 < arr[i].fr) {
                if (L != -1)
                    add_seg(L, R);
                L = arr[i].fr;
                R = arr[i].sc;
            } else
                R = max(R, arr[i].sc);
        }
        if (L != -1)
            add_seg(L, R);
    }
    ll ans = 0;
    sort(ind, ind + szind);
    szind = unique(ind, ind + szind) - ind;
    {
        int it = 0;
        for (int i = 0; i < szind; i++) {
            while (it < szseg && seg[it].sc < ind[i])
                it++;
            if (it < szseg && seg[it].fr <= ind[i])
                good[i] = 1;
        }
    }
    sort(mas, mas + szmas);
    ll last = 0;
    int L = 0, R = 0;
    while (L < szmas) {
        ans += cur * (mas[L].fr.fr - last);
        while (R < szmas && mas[R].fr.fr == mas[L].fr.fr) {
            if (mas[R].fr.sc == 0)
                add(mas[R].sc);
            else
                rem(mas[R].sc);
            R++;
        }
        last = mas[L].fr.fr;
        L = R;
    }
    ans += cur * (y - last);
    cout << ans << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 11 ms 1272 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 1272 KB Output is correct
17 Correct 90 ms 9592 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 4 ms 508 KB Output is correct
5 Correct 493 ms 40896 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1006 ms 95412 KB Output is correct
3 Correct 646 ms 53164 KB Output is correct
4 Correct 664 ms 53240 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1006 ms 95412 KB Output is correct
3 Correct 646 ms 53164 KB Output is correct
4 Correct 664 ms 53240 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 1758 ms 182880 KB Output is correct
7 Correct 1002 ms 93776 KB Output is correct
8 Correct 1740 ms 182792 KB Output is correct
9 Correct 1852 ms 182396 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1006 ms 95412 KB Output is correct
3 Correct 646 ms 53164 KB Output is correct
4 Correct 664 ms 53240 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 149 ms 15608 KB Output is correct
7 Correct 174 ms 18680 KB Output is correct
8 Correct 165 ms 18680 KB Output is correct
9 Correct 174 ms 18764 KB Output is correct
10 Correct 147 ms 13944 KB Output is correct
11 Correct 183 ms 18656 KB Output is correct
12 Correct 173 ms 18808 KB Output is correct
13 Correct 176 ms 18552 KB Output is correct
14 Correct 77 ms 9568 KB Output is correct
15 Correct 174 ms 15736 KB Output is correct
16 Correct 95 ms 9732 KB Output is correct
17 Correct 187 ms 18684 KB Output is correct
18 Correct 2013 ms 183064 KB Output is correct
19 Correct 2129 ms 182696 KB Output is correct
20 Correct 2244 ms 182608 KB Output is correct
21 Correct 202 ms 18552 KB Output is correct
22 Correct 173 ms 18588 KB Output is correct
23 Correct 231 ms 18424 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 82 ms 9592 KB Output is correct
3 Correct 106 ms 9592 KB Output is correct
4 Correct 1594 ms 115984 KB Output is correct
5 Correct 114 ms 10104 KB Output is correct
6 Correct 121 ms 9948 KB Output is correct
7 Correct 111 ms 9976 KB Output is correct
8 Correct 125 ms 10776 KB Output is correct
9 Correct 124 ms 10744 KB Output is correct
10 Correct 92 ms 9528 KB Output is correct
11 Correct 78 ms 9592 KB Output is correct
12 Correct 82 ms 9480 KB Output is correct
13 Correct 116 ms 10184 KB Output is correct
14 Correct 1016 ms 92380 KB Output is correct
15 Correct 89 ms 9492 KB Output is correct
16 Correct 854 ms 92408 KB Output is correct
17 Correct 1491 ms 114420 KB Output is correct
18 Incorrect 3 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 11 ms 1272 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 1272 KB Output is correct
17 Correct 90 ms 9592 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct