답안 #798682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
798682	2023-07-30T22:58:56 Z	Johann	Diversity (CEOI21_diversity)	C++14	22 / 100	26 ms	9812 KB

diversity

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;
int N, Q;
vi A, AA;
ll ans;

vi split(int x)
{
    vi sp;
    int j = 0;
    while (2 * (1 << j) <= x)
    {
        sp.push_back(1 << j);
        x -= 1 << j;
        sp.push_back(1 << j);
        x -= 1 << j;
        ++j;
    }
    j = 0;
    while (x > 0)
    {
        if (x & (1 << j))
            sp.push_back(1 << j), x ^= 1 << j;
        ++j;
    }
    return sp;
}

ll numberOfSubsequences(ll n)
{
    return n * (n + 1) / 2;
}
ll totalLengthOfSubsequences(ll n)
{
    return n * (n + 1) * (n + 1) / 2 - (2 * n + 1) * (n + 1) * n / 6;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
    AA.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> AA[i];

    while (Q--)
    {
        {
            int l, r;
            cin >> l >> r;
            --l;
            A = vi(AA.begin() + l, AA.begin() + r);
        }
        ll n = sz(A);

        vi heatMap(*max_element(all(A)) + 1, 0);
        for (int i = 0; i < sz(A); ++i)
            ++heatMap[A[i]];
        map<int, int> cnts;
        for (int i = 0; i < sz(heatMap); ++i)
            if (heatMap[i])
                ++cnts[heatMap[i]];

        vpii S;
        for (auto it = cnts.begin(); it != cnts.end(); ++it)
            for (int x : split(it->second))
                S.push_back({it->first, x});

        ll pref = 0;
        int num = sz(S);

        vi dp[2];
        for (int foo = 0; foo < 2; ++foo)
            dp[foo].reserve(N + 1), dp[foo].resize(N + 1);
        fill(all(dp[0]), INF);
        dp[0][0] = totalLengthOfSubsequences(n);

        for (int j = 0; j < num; ++j)
        {
            int ii = j & 1;
            int ni = ii ^ 1;
            fill(all(dp[ni]), INF);

            ll x = S[j].first;  // how much
            ll y = S[j].second; // how often
            ll len = x * y;

            ll subsure = 0;
            // if both are in set
            subsure += y * (totalLengthOfSubsequences(x) - numberOfSubsequences(x));
            for (int i = 2; i <= y; ++i)
                subsure += x * x * (y - i + 1) * i * (x - 1);

            // either with left or right endpoint in set
            ll factor = len * (len + 1) / 2 - x * y * (y + 1) / 2;
            subsure += factor * (n - len);

            for (ll left = 0; left < sz(dp[ii]); ++left)
            {
                ll tmp = dp[ii][left];
                if (tmp == INF)
                    continue;
                tmp -= subsure;

                // left
                dp[ni][left + len] = min(dp[ni][left + len], tmp - (len - y) * left * (n - left - len));
                // right
                ll right = pref - left;
                dp[ni][left] = min(dp[ni][left], tmp - (len - y) * right * (n - right - len));
            }
            pref += len;
        }
        ans = *min_element(all(dp[num & 1]));
        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
4.0 / 4.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	316 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	6 ms	3436 KB	Output is correct
5	Correct	12 ms	6484 KB	Output is correct
6	Correct	19 ms	9684 KB	Output is correct
7	Correct	19 ms	9684 KB	Output is correct
8	Correct	20 ms	9732 KB	Output is correct
9	Correct	19 ms	9720 KB	Output is correct
10	Correct	19 ms	9720 KB	Output is correct
11	Correct	22 ms	9812 KB	Output is correct
12	Correct	20 ms	9720 KB	Output is correct
13	Correct	19 ms	9716 KB	Output is correct
14	Correct	19 ms	9684 KB	Output is correct
15	Correct	20 ms	9684 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	6 ms	3436 KB	Output is correct
5	Correct	12 ms	6484 KB	Output is correct
6	Correct	19 ms	9684 KB	Output is correct
7	Correct	19 ms	9684 KB	Output is correct
8	Correct	20 ms	9732 KB	Output is correct
9	Correct	19 ms	9720 KB	Output is correct
10	Correct	19 ms	9720 KB	Output is correct
11	Correct	22 ms	9812 KB	Output is correct
12	Correct	20 ms	9720 KB	Output is correct
13	Correct	19 ms	9716 KB	Output is correct
14	Correct	19 ms	9684 KB	Output is correct
15	Correct	20 ms	9684 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	596 KB	Output is correct
19	Correct	8 ms	3412 KB	Output is correct
20	Correct	17 ms	6540 KB	Output is correct
21	Correct	25 ms	9720 KB	Output is correct
22	Correct	26 ms	9684 KB	Output is correct
23	Correct	26 ms	9716 KB	Output is correct
24	Correct	25 ms	9716 KB	Output is correct
25	Correct	26 ms	9720 KB	Output is correct
26	Correct	26 ms	9720 KB	Output is correct
27	Correct	25 ms	9692 KB	Output is correct
28	Correct	25 ms	9724 KB	Output is correct
29	Correct	26 ms	9596 KB	Output is correct
30	Correct	25 ms	9728 KB	Output is correct

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	6 ms	3436 KB	Output is correct
5	Correct	12 ms	6484 KB	Output is correct
6	Correct	19 ms	9684 KB	Output is correct
7	Correct	19 ms	9684 KB	Output is correct
8	Correct	20 ms	9732 KB	Output is correct
9	Correct	19 ms	9720 KB	Output is correct
10	Correct	19 ms	9720 KB	Output is correct
11	Correct	22 ms	9812 KB	Output is correct
12	Correct	20 ms	9720 KB	Output is correct
13	Correct	19 ms	9716 KB	Output is correct
14	Correct	19 ms	9684 KB	Output is correct
15	Correct	20 ms	9684 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	596 KB	Output is correct
19	Correct	8 ms	3412 KB	Output is correct
20	Correct	17 ms	6540 KB	Output is correct
21	Correct	25 ms	9720 KB	Output is correct
22	Correct	26 ms	9684 KB	Output is correct
23	Correct	26 ms	9716 KB	Output is correct
24	Correct	25 ms	9716 KB	Output is correct
25	Correct	26 ms	9720 KB	Output is correct
26	Correct	26 ms	9720 KB	Output is correct
27	Correct	25 ms	9692 KB	Output is correct
28	Correct	25 ms	9724 KB	Output is correct
29	Correct	26 ms	9596 KB	Output is correct
30	Correct	25 ms	9728 KB	Output is correct
31	Incorrect	0 ms	340 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	596 KB	Output is correct
14	Correct	6 ms	3436 KB	Output is correct
15	Correct	12 ms	6484 KB	Output is correct
16	Correct	19 ms	9684 KB	Output is correct
17	Correct	19 ms	9684 KB	Output is correct
18	Correct	20 ms	9732 KB	Output is correct
19	Correct	19 ms	9720 KB	Output is correct
20	Correct	19 ms	9720 KB	Output is correct
21	Correct	22 ms	9812 KB	Output is correct
22	Correct	20 ms	9720 KB	Output is correct
23	Correct	19 ms	9716 KB	Output is correct
24	Correct	19 ms	9684 KB	Output is correct
25	Correct	20 ms	9684 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct
29	Correct	8 ms	3412 KB	Output is correct
30	Correct	17 ms	6540 KB	Output is correct
31	Correct	25 ms	9720 KB	Output is correct
32	Correct	26 ms	9684 KB	Output is correct
33	Correct	26 ms	9716 KB	Output is correct
34	Correct	25 ms	9716 KB	Output is correct
35	Correct	26 ms	9720 KB	Output is correct
36	Correct	26 ms	9720 KB	Output is correct
37	Correct	25 ms	9692 KB	Output is correct
38	Correct	25 ms	9724 KB	Output is correct
39	Correct	26 ms	9596 KB	Output is correct
40	Correct	25 ms	9728 KB	Output is correct
41	Incorrect	0 ms	340 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Subtask #6
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	596 KB	Output is correct
14	Correct	6 ms	3436 KB	Output is correct
15	Correct	12 ms	6484 KB	Output is correct
16	Correct	19 ms	9684 KB	Output is correct
17	Correct	19 ms	9684 KB	Output is correct
18	Correct	20 ms	9732 KB	Output is correct
19	Correct	19 ms	9720 KB	Output is correct
20	Correct	19 ms	9720 KB	Output is correct
21	Correct	22 ms	9812 KB	Output is correct
22	Correct	20 ms	9720 KB	Output is correct
23	Correct	19 ms	9716 KB	Output is correct
24	Correct	19 ms	9684 KB	Output is correct
25	Correct	20 ms	9684 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct
29	Correct	8 ms	3412 KB	Output is correct
30	Correct	17 ms	6540 KB	Output is correct
31	Correct	25 ms	9720 KB	Output is correct
32	Correct	26 ms	9684 KB	Output is correct
33	Correct	26 ms	9716 KB	Output is correct
34	Correct	25 ms	9716 KB	Output is correct
35	Correct	26 ms	9720 KB	Output is correct
36	Correct	26 ms	9720 KB	Output is correct
37	Correct	25 ms	9692 KB	Output is correct
38	Correct	25 ms	9724 KB	Output is correct
39	Correct	26 ms	9596 KB	Output is correct
40	Correct	25 ms	9728 KB	Output is correct
41	Incorrect	0 ms	340 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #798682

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 10.0 / 10.0

Subtask #3 8.0 / 8.0

Subtask #4 0 / 16.0

Subtask #5 0 / 26.0

Subtask #6 0 / 36.0

Subtask #1
4.0 / 4.0

Subtask #2
10.0 / 10.0

Subtask #3
8.0 / 8.0

Subtask #4
0 / 16.0

Subtask #5
0 / 26.0

Subtask #6
0 / 36.0