oj.uz

Submission #492947

# Submission time Handle Problem Language Result Execution time Memory
492947 2021-12-09T20:17:50 Z blue Diversity (CEOI21_diversity) C++17
4 / 100
 3 ms 6988 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <deque>
using namespace std;

const int mx = 300'000;
const int mxQ = 50'000;
const int rt = 500;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define sz(x) (int(x.size()))

int N, Q;
vi a(1+mx);

vi l(1+mxQ), r(1+mxQ);
vll ans(1+mxQ);

int L = 1;
int R = 0;

vll ct(1+mx, 0);
vll freq(1+mx, 0);

vector<ll> sizes;
vector<bool> occ(1+mx, 0);

ll ap_sum(ll a, ll d, ll n)
{
    return (n * (2*a + (n-1)*d))/2;
}

ll ap_sq_sum(ll a, ll d, ll n)
{
    /*
    a^2 + (a+d)^2 + ... + (a+(n-1)*d)^2
    = n * a^2   +   2*a*(0d + 1d + ... + (n-1)d)   +   0d^2 + d^2 + ... (n-1)d ^ 2
    = n*a^2  +  2*a*d * (n-1)*n/2   +   d^2 * (n-1)*(n)*(2n-1)/6
    */
    assert(d*n <= 300'000);
    assert(d*d*n*n*2*n <= 1'000'000'000'000'0000);

    return n*a*a  +  a*d*(n-1)*n   +   d*d*(((n-1)*n*(2*n-1))/6LL);
}

ll get_ans()
{
    vector<ll> sizes2;
    for(ll s: sizes)
    {
        if(occ[s]) continue;
        if(freq[s] == 0) continue;
        sizes2.push_back(s);
        occ[s] = 1;
    }
    sizes = sizes2;
    for(ll s: sizes) occ[s] = 0;

    sort(sizes.begin(), sizes.end(), [] (int u, int v)
    {
        return u > v;
    });

    deque< pair<ll, ll> > ord;
    int z = 0;
    for(ll s: sizes)
    {
        if(freq[s] % 2 == 1)
        {
            if(z) ord.push_back({s, 1});
            else ord.push_front({s, 1});
            z = !z;
        }

        if(freq[s]/2)
        {
            ord.push_back({s, freq[s]/2});
            ord.push_front({s, freq[s]/2});
        }
    }
    ord.push_front({0, 0});

    /*vll prefsum(1, 0);
    for(auto o: ord)
    {
        for(int y = 1; y <= o.second; y++)
        {
            prefsum.push_back(prefsum.back() + o.first);
        }
    }

    ll ans = 0;

    int P = sz(prefsum) - 1;

    for(int i = 1; i <= P; i++)
    {
        ans += ((prefsum[i] - prefsum[i-1])*(prefsum[i] - prefsum[i-1] + 1))/2;
        ans += (prefsum[i] - prefsum[i-1])*prefsum[i-1];
        ans += (prefsum[i] - prefsum[i-1])*(prefsum[P] - prefsum[i]);
        ans += (prefsum[P] - prefsum[i])*prefsum[i-1];



    }*/

    ll ans = 0;
    ll tot = 0;

    int P = sz(ord);
    vll prefsum(1+P, 0);
    for(int i = 1; i <= P; i++)
    {
        prefsum[i] = prefsum[i-1] + (ord[i].first * ord[i].second);
    }
    tot = prefsum[P];

    for(int i = 1; i <= P; i++)
    {
        ans += ord[i].second * (ord[i].first * (ord[i].first + 1))/2;
        ans -= ap_sq_sum(prefsum[i-1], ord[i].first, ord[i].second);
        ans += ord[i].second * (ord[i].first * (tot - ord[i].first));
        ans += (tot - ord[i].first) * ap_sum(prefsum[i-1], ord[i].first, ord[i].second);
    }

    return ans;
}

void add_species(int a)
{
    freq[ct[a]]--;
    ct[a]++;
    freq[ct[a]]++;
    sizes.push_back(ct[a]);
}

void remove_species(int a)
{
    freq[ct[a]]--;
    ct[a]--;
    freq[ct[a]]++;
    sizes.push_back(ct[a]);
}

void expand_right()
{
    R++;
    add_species(a[R]);
}

void expand_left()
{
    L--;
    add_species(a[L]);
}

void contract_right()
{
    remove_species(a[R]);
    R--;
}

void contract_left()
{
    remove_species(a[L]);
    L++;
}

int main()
{
    cin >> N >> Q;
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int j = 1; j <= Q; j++) cin >> l[j] >> r[j];

    vi I(Q);
    for(int j = 0; j < Q; j++) I[j] = j+1;
    sort(I.begin(), I.end(), [] (int u, int v)
    {
        if(l[u]/rt != l[v]/rt) return l[u]/rt < l[v]/rt;
        else return r[u] < r[v];
    });

    freq[0] = mx;

    for(int q: I)
    {
        while(R < r[q]) expand_right();
        while(L > l[q]) expand_left();
        while(R > r[q]) contract_right();
        while(L < l[q]) contract_left();
        ans[q] = get_ans();
    }

    for(int q = 1; q <= Q; q++) cout << ans[q] << '\n';
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6988 KB Output is correct
2 Correct 3 ms 6988 KB Output is correct
3 Correct 3 ms 6988 KB Output is correct
4 Correct 3 ms 6988 KB Output is correct
5 Correct 3 ms 6988 KB Output is correct
6 Correct 2 ms 6988 KB Output is correct
7 Correct 3 ms 6988 KB Output is correct
8 Correct 3 ms 6988 KB Output is correct
9 Correct 3 ms 6988 KB Output is correct
10 Correct 3 ms 6988 KB Output is correct
11 Incorrect 3 ms 6988 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6988 KB Output is correct
2 Correct 3 ms 6988 KB Output is correct
3 Correct 3 ms 6988 KB Output is correct
4 Correct 3 ms 6988 KB Output is correct
5 Correct 3 ms 6988 KB Output is correct
6 Correct 2 ms 6988 KB Output is correct
7 Correct 3 ms 6988 KB Output is correct
8 Correct 3 ms 6988 KB Output is correct
9 Correct 3 ms 6988 KB Output is correct
10 Correct 3 ms 6988 KB Output is correct
11 Incorrect 3 ms 6988 KB Output isn't correct
12 Halted 0 ms 0 KB -