Submission #1318317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318317		spetr	Diversity (CEOI21_diversity)	C++20	0 / 100	1 ms	412 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

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

    ll n, q;
    if (!(cin >> n >> q)) return 0;
    
    vl nums(n);
    // Použijeme mapu pro bezpečné počítání četností (funguje i pro velká čísla druhů)
    map<ll, ll> counts;
    
    for (ll i = 0; i < n; i++){
        cin >> nums[i];
        counts[nums[i]]++;
    }
    
    ll l, r;
    cin >> l >> r;

    // Vytvoříme páry {četnost, druh} pouze pro unikátní druhy
    vector<pl> pary;
    for (auto const& [species, count] : counts) {
        pary.push_back({count, species});
    }
    
    // Seřadíme podle četnosti (méně četné druhy na začátek)
    sort(pary.begin(), pary.end());
    
    nums.clear();
    // Rekonstrukce pole - nyní bude mít správnou délku N
    for (auto x : pary){
        for (ll i = 0; i < x.first; i++){
            nums.push_back(x.second);
        }
    }
    
    // DP výpočet celkové diverzity
    // dp[i] = součet diverzit všech podposloupností končících na indexu i
    vl dp (n, 1);
    
    // Base case pro index 0 je již nastaven na 1
    for (ll i = 1; i < n; i++){
        if (nums[i] == nums[i-1]){
            // Pokud je zvíře stejné jako předchozí, diverzita se zvedne jen o 1 (pro samotné nové zvíře)
            // v rámci existujících podposloupností se "nepřičítá", protože druh už tam je.
            dp[i] = dp[i-1] + 1;
        }
        else{
            // Pokud je to nové zvíře (vzhledem k seřazení a seskupení to znamená, 
            // že tento druh se v předchozích podposloupnostech končících na i-1 nevyskytoval),
            // zvýší diverzitu všech (i+1) podposloupností končících na i o 1.
            dp[i] = dp[i-1] + (i + 1);
        }
    }
    
    ll suma = 0;
    for (ll i = 0; i < n; i++){
        suma += dp[i];
    }
    
    cout << suma << "\n";

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36