oj.uz

Submission #120506

# Submission time Handle Problem Language Result Execution time Memory
120506 2019-06-24T17:18:03 Z model_code Strange Device (APIO19_strange_device) C++17
45 / 100
 2178 ms 145856 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 = 2e6 + 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 10 ms 1272 KB Output is correct
4 Correct 2 ms 376 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 2 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 2 ms 376 KB Output is correct
12 Correct 5 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 3 ms 380 KB Output is correct
16 Correct 12 ms 1272 KB Output is correct
17 Correct 91 ms 9592 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 4 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 4 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 501 ms 18040 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 388 KB Output is correct
2 Correct 1010 ms 60936 KB Output is correct
3 Correct 644 ms 16068 KB Output is correct
4 Correct 742 ms 15984 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 388 KB Output is correct
2 Correct 1010 ms 60936 KB Output is correct
3 Correct 644 ms 16068 KB Output is correct
4 Correct 742 ms 15984 KB Output is correct
5 Correct 0 ms 380 KB Output is correct
6 Correct 1899 ms 145436 KB Output is correct
7 Correct 992 ms 56596 KB Output is correct
8 Correct 1716 ms 145580 KB Output is correct
9 Correct 1844 ms 145192 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 388 KB Output is correct
2 Correct 1010 ms 60936 KB Output is correct
3 Correct 644 ms 16068 KB Output is correct
4 Correct 742 ms 15984 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 148 ms 11864 KB Output is correct
7 Correct 173 ms 14992 KB Output is correct
8 Correct 164 ms 14880 KB Output is correct
9 Correct 166 ms 15028 KB Output is correct
10 Correct 147 ms 10220 KB Output is correct
11 Correct 177 ms 15096 KB Output is correct
12 Correct 169 ms 14980 KB Output is correct
13 Correct 178 ms 15020 KB Output is correct
14 Correct 76 ms 5880 KB Output is correct
15 Correct 182 ms 11932 KB Output is correct
16 Correct 93 ms 5880 KB Output is correct
17 Correct 183 ms 14896 KB Output is correct
18 Correct 2020 ms 145856 KB Output is correct
19 Correct 2039 ms 145500 KB Output is correct
20 Correct 2178 ms 145260 KB Output is correct
21 Correct 202 ms 14940 KB Output is correct
22 Correct 174 ms 14968 KB Output is correct
23 Correct 205 ms 5812 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 80 ms 5880 KB Output is correct
3 Correct 104 ms 5980 KB Output is correct
4 Correct 1593 ms 79040 KB Output is correct
5 Correct 113 ms 6392 KB Output is correct
6 Correct 113 ms 6392 KB Output is correct
7 Correct 108 ms 6376 KB Output is correct
8 Correct 125 ms 7216 KB Output is correct
9 Correct 127 ms 7160 KB Output is correct
10 Correct 90 ms 5880 KB Output is correct
11 Correct 77 ms 5852 KB Output is correct
12 Correct 77 ms 5880 KB Output is correct
13 Correct 116 ms 6520 KB Output is correct
14 Correct 979 ms 55544 KB Output is correct
15 Correct 83 ms 5880 KB Output is correct
16 Correct 842 ms 55160 KB Output is correct
17 Correct 1468 ms 77264 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Correct 10 ms 1272 KB Output is correct
4 Correct 2 ms 376 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 2 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 2 ms 376 KB Output is correct
12 Correct 5 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 3 ms 380 KB Output is correct
16 Correct 12 ms 1272 KB Output is correct
17 Correct 91 ms 9592 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Incorrect 4 ms 376 KB Output isn't correct