oj.uz

Submission #520467

# Submission time Handle Problem Language Result Execution time Memory
520467 2022-01-30T05:51:12 Z KoD Diversity (CEOI21_diversity) C++17
22 / 100
 7000 ms 524292 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

constexpr int B = 500;
constexpr int MAX = 300000;

constexpr i64 sum_k(const int n) {
    return (i64)n * (n + 1) / 2;
}
 
constexpr i64 sum_k2(const int n) {
    return (i64)n * (n + 1) * (2 * n + 1) / 6;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    vector<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
        x -= 1;
    }
    const int G = N / B;
    vector precalc(G + 1, vector<vector<pair<int, int>>>(G + 1));
    for (int lc = 0; lc < G; ++lc) {
        vector<char> appear(MAX);
        vector<int> count(MAX);
        for (int rc = lc + 1; rc <= G; ++rc) {
            vector<int> remove, add;
            for (int i = B * (rc - 1); i < B * rc; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    if (count[A[i]] > 0) {
                        remove.push_back(count[A[i]]);
                    }
                    add.push_back(A[i]);
                }
                count[A[i]] += 1;
            }
            for (auto& x : add) {
                appear[x] = false;
                x = count[x];
            }
            std::sort(remove.begin(), remove.end());
            std::sort(add.begin(), add.end());
            const auto& read = precalc[lc][rc - 1];
            auto& write = precalc[lc][rc];
            const int A = read.size(), B = remove.size(), C = add.size();
            int i = 0, j = 0, k = 0;
            while (i < A or k < C) {
                int val = MAX;
                if (i < A) {
                    val = std::min(val, read[i].first);
                }
                if (k < C) {
                    val = std::min(val, add[k]);
                }
                int cnt = 0;
                if (i < A and val == read[i].first) {
                    cnt += read[i].second;
                    i += 1;
                }
                while (j < B and val == remove[j]) {
                    j += 1;
                    cnt -= 1;
                }
                while (k < C and val == add[k]) {
                    k += 1;
                    cnt += 1;
                }
                if (cnt > 0) {
                    write.emplace_back(val, cnt);
                }
            }
        }
    }
    vector<vector<int>> idx(MAX);
    for (int i = 0; i < N; ++i) {
        idx[A[i]].push_back(i);
    }
    const auto range_count = [&](const int l, const int r, const int x) {
        const auto& v = idx[x];
        return std::lower_bound(v.begin(), v.end(), r) - std::lower_bound(v.begin(), v.end(), l);
    };
    vector<char> appear(MAX);
    vector<int> count(MAX);
    while (Q--) {
        int l, r;
        std::cin >> l >> r;
        l -= 1;
        vector<pair<int, int>> list;
        if (l / B == r / B) {
            vector<int> add;
            for (int i = l; i < r; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    add.push_back(A[i]);
                }
                count[A[i]] += 1;
            }
            for (const int x : add) {
                appear[x] = false;
                list.emplace_back(count[x], 1);
                count[x] = 0;
            }
            std::sort(list.begin(), list.end());
        } else {
            const int lc = (l + B - 1) / B;
            const int rc = r / B;
            assert(lc <= rc);
            vector<int> remove, add, seen;
            for (int i = l; i < B * lc; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    const int tmp = range_count(B * lc, B * rc, A[i]);
                    if (tmp > 0) {
                        remove.push_back(tmp);
                    }
                    add.push_back(range_count(l, r, A[i]));
                    seen.push_back(A[i]);
                }
            } 
            for (int i = B * rc; i < r; ++i) {
                if (!appear[A[i]]) {
                    appear[A[i]] = true;
                    const int tmp = range_count(B * lc, B * rc, A[i]);
                    if (tmp > 0) {
                        remove.push_back(tmp);
                    }
                    add.push_back(range_count(l, r, A[i]));
                    seen.push_back(A[i]);
                }
            } 
            for (const int x : seen) {
                appear[x] = false;
            }
            std::sort(remove.begin(), remove.end());
            std::sort(add.begin(), add.end());
            const auto& read = precalc[lc][rc];
            const int A = read.size(), B = remove.size(), C = add.size();
            int i = 0, j = 0, k = 0;
            while (i < A or k < C) {
                int val = MAX;
                if (i < A) {
                    val = std::min(val, read[i].first);
                }
                if (k < C) {
                    val = std::min(val, add[k]);
                }
                int cnt = 0;
                if (i < A and val == read[i].first) {
                    cnt += read[i].second;
                    i += 1;
                }
                while (j < B and val == remove[j]) {
                    j += 1;
                    cnt -= 1;
                }
                while (k < C and val == add[k]) {
                    k += 1;
                    cnt += 1;
                }
                if (cnt > 0) {
                    list.emplace_back(val, cnt);
                }
            }
        }
        const int len = r - l;
        i64 ans = sum_k(len);
        const auto add_to = [&](const i64 s, const int a, const int n) {
            ans += (n * s + sum_k(n) * a) * len;
            ans -= n * s * s + 2 * s * sum_k(n) * a + sum_k2(n) * a * a;
        };
        int left = 0, right = 0;
        for (const auto& [a, b] : list) {
            assert(a > 0 and b > 0);
            if (left > right) {
                std::swap(left, right);
            }
            const int need = std::min(b, (right - left + a - 1) / a);
            const int to_left = need + (b - need) / 2;
            const int to_right = b - to_left;
            add_to(left, a, to_left);
            add_to(right, a, to_right);
            left += a * to_left;
            right += a * to_right;
        }
        ans -= (i64)left * (len - left);
        std::cout << ans << '\n';
    }
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 4 ms 8780 KB Output is correct
3 Correct 4 ms 8780 KB Output is correct
4 Correct 5 ms 8780 KB Output is correct
5 Correct 4 ms 8780 KB Output is correct
6 Correct 5 ms 8780 KB Output is correct
7 Correct 4 ms 8780 KB Output is correct
8 Correct 5 ms 8780 KB Output is correct
9 Correct 4 ms 8780 KB Output is correct
10 Correct 4 ms 8780 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 5 ms 9956 KB Output is correct
3 Correct 8 ms 10000 KB Output is correct
4 Correct 71 ms 14132 KB Output is correct
5 Correct 247 ms 26132 KB Output is correct
6 Correct 570 ms 45704 KB Output is correct
7 Correct 545 ms 45756 KB Output is correct
8 Correct 520 ms 45956 KB Output is correct
9 Correct 532 ms 45480 KB Output is correct
10 Correct 513 ms 45548 KB Output is correct
11 Correct 532 ms 45700 KB Output is correct
12 Correct 531 ms 45888 KB Output is correct
13 Correct 551 ms 45700 KB Output is correct
14 Correct 540 ms 45800 KB Output is correct
15 Correct 516 ms 45488 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 5 ms 9956 KB Output is correct
3 Correct 8 ms 10000 KB Output is correct
4 Correct 71 ms 14132 KB Output is correct
5 Correct 247 ms 26132 KB Output is correct
6 Correct 570 ms 45704 KB Output is correct
7 Correct 545 ms 45756 KB Output is correct
8 Correct 520 ms 45956 KB Output is correct
9 Correct 532 ms 45480 KB Output is correct
10 Correct 513 ms 45548 KB Output is correct
11 Correct 532 ms 45700 KB Output is correct
12 Correct 531 ms 45888 KB Output is correct
13 Correct 551 ms 45700 KB Output is correct
14 Correct 540 ms 45800 KB Output is correct
15 Correct 516 ms 45488 KB Output is correct
16 Correct 6 ms 8780 KB Output is correct
17 Correct 6 ms 10000 KB Output is correct
18 Correct 9 ms 10020 KB Output is correct
19 Correct 90 ms 16592 KB Output is correct
20 Correct 314 ms 36144 KB Output is correct
21 Correct 699 ms 68132 KB Output is correct
22 Correct 771 ms 68356 KB Output is correct
23 Correct 717 ms 68184 KB Output is correct
24 Correct 721 ms 68300 KB Output is correct
25 Correct 712 ms 68308 KB Output is correct
26 Correct 736 ms 68324 KB Output is correct
27 Correct 729 ms 68188 KB Output is correct
28 Correct 761 ms 68312 KB Output is correct
29 Correct 745 ms 68252 KB Output is correct
30 Correct 732 ms 68216 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 5 ms 9956 KB Output is correct
3 Correct 8 ms 10000 KB Output is correct
4 Correct 71 ms 14132 KB Output is correct
5 Correct 247 ms 26132 KB Output is correct
6 Correct 570 ms 45704 KB Output is correct
7 Correct 545 ms 45756 KB Output is correct
8 Correct 520 ms 45956 KB Output is correct
9 Correct 532 ms 45480 KB Output is correct
10 Correct 513 ms 45548 KB Output is correct
11 Correct 532 ms 45700 KB Output is correct
12 Correct 531 ms 45888 KB Output is correct
13 Correct 551 ms 45700 KB Output is correct
14 Correct 540 ms 45800 KB Output is correct
15 Correct 516 ms 45488 KB Output is correct
16 Correct 6 ms 8780 KB Output is correct
17 Correct 6 ms 10000 KB Output is correct
18 Correct 9 ms 10020 KB Output is correct
19 Correct 90 ms 16592 KB Output is correct
20 Correct 314 ms 36144 KB Output is correct
21 Correct 699 ms 68132 KB Output is correct
22 Correct 771 ms 68356 KB Output is correct
23 Correct 717 ms 68184 KB Output is correct
24 Correct 721 ms 68300 KB Output is correct
25 Correct 712 ms 68308 KB Output is correct
26 Correct 736 ms 68324 KB Output is correct
27 Correct 729 ms 68188 KB Output is correct
28 Correct 761 ms 68312 KB Output is correct
29 Correct 745 ms 68252 KB Output is correct
30 Correct 732 ms 68216 KB Output is correct
31 Correct 5 ms 8848 KB Output is correct
32 Correct 7 ms 8848 KB Output is correct
33 Correct 6 ms 8848 KB Output is correct
34 Correct 10 ms 10128 KB Output is correct
35 Correct 11 ms 10128 KB Output is correct
36 Correct 12 ms 10072 KB Output is correct
37 Correct 145 ms 16360 KB Output is correct
38 Correct 182 ms 14848 KB Output is correct
39 Correct 722 ms 39164 KB Output is correct
40 Correct 3069 ms 200824 KB Output is correct
41 Execution timed out 7039 ms 524292 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 4 ms 8780 KB Output is correct
3 Correct 4 ms 8780 KB Output is correct
4 Correct 5 ms 8780 KB Output is correct
5 Correct 4 ms 8780 KB Output is correct
6 Correct 5 ms 8780 KB Output is correct
7 Correct 4 ms 8780 KB Output is correct
8 Correct 5 ms 8780 KB Output is correct
9 Correct 4 ms 8780 KB Output is correct
10 Correct 4 ms 8780 KB Output is correct
11 Correct 5 ms 8780 KB Output is correct
12 Correct 5 ms 9956 KB Output is correct
13 Correct 8 ms 10000 KB Output is correct
14 Correct 71 ms 14132 KB Output is correct
15 Correct 247 ms 26132 KB Output is correct
16 Correct 570 ms 45704 KB Output is correct
17 Correct 545 ms 45756 KB Output is correct
18 Correct 520 ms 45956 KB Output is correct
19 Correct 532 ms 45480 KB Output is correct
20 Correct 513 ms 45548 KB Output is correct
21 Correct 532 ms 45700 KB Output is correct
22 Correct 531 ms 45888 KB Output is correct
23 Correct 551 ms 45700 KB Output is correct
24 Correct 540 ms 45800 KB Output is correct
25 Correct 516 ms 45488 KB Output is correct
26 Correct 6 ms 8780 KB Output is correct
27 Correct 6 ms 10000 KB Output is correct
28 Correct 9 ms 10020 KB Output is correct
29 Correct 90 ms 16592 KB Output is correct
30 Correct 314 ms 36144 KB Output is correct
31 Correct 699 ms 68132 KB Output is correct
32 Correct 771 ms 68356 KB Output is correct
33 Correct 717 ms 68184 KB Output is correct
34 Correct 721 ms 68300 KB Output is correct
35 Correct 712 ms 68308 KB Output is correct
36 Correct 736 ms 68324 KB Output is correct
37 Correct 729 ms 68188 KB Output is correct
38 Correct 761 ms 68312 KB Output is correct
39 Correct 745 ms 68252 KB Output is correct
40 Correct 732 ms 68216 KB Output is correct
41 Correct 5 ms 8848 KB Output is correct
42 Correct 7 ms 8848 KB Output is correct
43 Correct 6 ms 8848 KB Output is correct
44 Correct 10 ms 10128 KB Output is correct
45 Correct 11 ms 10128 KB Output is correct
46 Correct 12 ms 10072 KB Output is correct
47 Correct 145 ms 16360 KB Output is correct
48 Correct 182 ms 14848 KB Output is correct
49 Correct 722 ms 39164 KB Output is correct
50 Correct 3069 ms 200824 KB Output is correct
51 Execution timed out 7039 ms 524292 KB Time limit exceeded
52 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 4 ms 8780 KB Output is correct
3 Correct 4 ms 8780 KB Output is correct
4 Correct 5 ms 8780 KB Output is correct
5 Correct 4 ms 8780 KB Output is correct
6 Correct 5 ms 8780 KB Output is correct
7 Correct 4 ms 8780 KB Output is correct
8 Correct 5 ms 8780 KB Output is correct
9 Correct 4 ms 8780 KB Output is correct
10 Correct 4 ms 8780 KB Output is correct
11 Correct 5 ms 8780 KB Output is correct
12 Correct 5 ms 9956 KB Output is correct
13 Correct 8 ms 10000 KB Output is correct
14 Correct 71 ms 14132 KB Output is correct
15 Correct 247 ms 26132 KB Output is correct
16 Correct 570 ms 45704 KB Output is correct
17 Correct 545 ms 45756 KB Output is correct
18 Correct 520 ms 45956 KB Output is correct
19 Correct 532 ms 45480 KB Output is correct
20 Correct 513 ms 45548 KB Output is correct
21 Correct 532 ms 45700 KB Output is correct
22 Correct 531 ms 45888 KB Output is correct
23 Correct 551 ms 45700 KB Output is correct
24 Correct 540 ms 45800 KB Output is correct
25 Correct 516 ms 45488 KB Output is correct
26 Correct 6 ms 8780 KB Output is correct
27 Correct 6 ms 10000 KB Output is correct
28 Correct 9 ms 10020 KB Output is correct
29 Correct 90 ms 16592 KB Output is correct
30 Correct 314 ms 36144 KB Output is correct
31 Correct 699 ms 68132 KB Output is correct
32 Correct 771 ms 68356 KB Output is correct
33 Correct 717 ms 68184 KB Output is correct
34 Correct 721 ms 68300 KB Output is correct
35 Correct 712 ms 68308 KB Output is correct
36 Correct 736 ms 68324 KB Output is correct
37 Correct 729 ms 68188 KB Output is correct
38 Correct 761 ms 68312 KB Output is correct
39 Correct 745 ms 68252 KB Output is correct
40 Correct 732 ms 68216 KB Output is correct
41 Correct 5 ms 8848 KB Output is correct
42 Correct 7 ms 8848 KB Output is correct
43 Correct 6 ms 8848 KB Output is correct
44 Correct 10 ms 10128 KB Output is correct
45 Correct 11 ms 10128 KB Output is correct
46 Correct 12 ms 10072 KB Output is correct
47 Correct 145 ms 16360 KB Output is correct
48 Correct 182 ms 14848 KB Output is correct
49 Correct 722 ms 39164 KB Output is correct
50 Correct 3069 ms 200824 KB Output is correct
51 Execution timed out 7039 ms 524292 KB Time limit exceeded
52 Halted 0 ms 0 KB -