oj.uz

Submission #492931

# Submission time Handle Problem Language Result Execution time Memory
492931 2021-12-09T19:30:12 Z blue Diversity (CEOI21_diversity) C++17
0 / 100
 2 ms 1484 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

using ll = long long;

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<int> ct(1+300'000, 0);
    for(int i = 1; i <= N; i++)
    {
        int a;
        cin >> a;
        ct[a]++;
    }

    int l, r;
    cin >> l >> r;

    vector<ll> val;
    for(int f = 1; f <= 300'000; f++)
        if(ct[f])
            val.push_back(ct[f]);

    sort(val.begin(), val.end());

    deque<ll> val2;
    for(int i = 0; i < int(val.size()); i++)
    {
        if(i % 2 == 0) val2.push_back(val[i]);
        else val2.push_front(val[i]);
    }
    val2.push_front(0);

    int G = int(val2.size()) - 1;

    vector<ll> prefsum(1+G, 0);
    for(int i = 1; i <= G; i++) prefsum[i] = prefsum[i-1] + val2[i];

    // for(int f = 1; f <= G; f++) cerr << val2[f] << ' ';
    // cerr << '\n';

    ll res = 0;
    for(int i = 1; i <= G; i++)
    {
        res += (val2[i]*(val2[i]+1))/2 + prefsum[i-1]*val2[i] + (prefsum[G] - prefsum[i])*val2[i] + (prefsum[i-1])*(prefsum[G] - prefsum[i]);
        // cerr << "!\n";
        // cerr << (prefsum[G] - prefsum[i])*val2[i] << '\n';
        // cerr << (val2[i]*(val2[i]+1))/2 << '\n';
        // cerr << prefsum[i-1]*val2[i] << '\n';
        // cerr << (prefsum[i-1])*(prefsum[G] - prefsum[i]) << '\n';
        // cerr << i << " : " << (val2[i]*(val2[i]+1))/2 + prefsum[i-1]*val2[i] + (prefsum[G] - prefsum[i])*val2[i] * (prefsum[i-1])*(prefsum[G] - prefsum[i]);
        // cerr << '\n';
    }

    cout << res << '\n';
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 26.0

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

Subtask #6
0 / 36.0

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