Submission #474214

#	Time	Username	Problem	Language	Result	Execution time	Memory
474214		JovanB	Diversity (CEOI21_diversity)	C++17	100 / 100	4977 ms	476616 KiB

diversity

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

using ll = long long;
using ld = long double;

const int N = 300000;

ll dp[(1<<23)];
int ima[N+5];

const ll INF = 1000000000000000000LL;

const int K = 200;
const int BLOCK = 400;

struct qvry{
    int l, r, ind;
    bool operator <(const qvry &b){
        if(l/BLOCK == b.l/BLOCK) return r < b.r;
        return l/BLOCK < b.l/BLOCK;
    }
};

bool ins[N+5];
int cnt[N+5];
int tren[N+5];
ll pref[K+5][N+5];

vector <int> vals;

void Dodaj(int i){
    cnt[tren[i]]--;
    tren[i]++;
    cnt[tren[i]]++;
    if(cnt[tren[i]] == 1) vals.push_back(tren[i]);
}

void Brisi(int i){
    cnt[tren[i]]--;
    tren[i]--;
    cnt[tren[i]]++;
    if(cnt[tren[i]] == 1) vals.push_back(tren[i]);
}

ll sol[N+5];
int niz[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    for(int i=1; i<=K; i++){
        for(int j=1; j<=N; j++){
            pref[i][j] = 1LL*j*(j+1)/2;
            if(j > i) pref[i][j] += pref[i][j-i];
        }
    }
    int n, qrs;
    cin >> n >> qrs;
    vector <int> vec;
    for(int i=1; i<=n; i++){
        cin >> niz[i];
    }
    vector <qvry> queries;
    for(int i=1; i<=qrs; i++){
        int l, r;
        cin >> l >> r;
        queries.push_back({l, r, i});
    }
    sort(queries.begin(), queries.end());
    int tl = 1, tr = 1;
    Dodaj(niz[1]);
    for(auto qry : queries){
        int l = qry.l;
        int r = qry.r;
        int ind = qry.ind;
        while(tr < r) tr++, Dodaj(niz[tr]);
        while(tl > l) tl--, Dodaj(niz[tl]);
        while(tr > r) Brisi(niz[tr]), tr--;
        while(tl < l) Brisi(niz[tl]), tl++;
        vector <int> nvals;
        for(auto c : vals){
            if(!cnt[c] || c == 0 || ins[c]) continue;
            ins[c] = 1;
            nvals.push_back(c);
        }
        swap(vals, nvals);
        nvals.clear();
        sort(vals.begin(), vals.end());
        int tl = 0, tr = 0, bl = 0, br = 0;
        int len = r - l + 1;
        ll res = 0;
        for(auto x : vals){
            int c = cnt[x];
            res += 1LL*len*(len+1)*c/2;
            if(x > K){
                while(c--){
                    if(br < bl){
                        res -= 1LL*tr*(tr+1)/2;
                        res -= 1LL*(len-tr-x)*(len-tr-x+1)/2;
                        tr += x;
                        br++;
                    }
                    else{
                        res -= 1LL*tl*(tl+1)/2;
                        res -= 1LL*(len-tl-x)*(len-tl-x+1)/2;
                        tl += x;
                        bl++;
                    }
                }
                continue;
            }
            if(br < bl){
                res -= 1LL*tr*(tr+1)/2;
                res -= 1LL*(len-tr-x)*(len-tr-x+1)/2;
                tr += x;
                br++;
                c--;
            }

            int dod = (c+1)/2;
            if(dod == 0) continue;
            /// tl, tl + x, ..., tl + (dod-1)* x
            res -= pref[x][tl + (dod-1)*x];
            if(tl > x) res += pref[x][tl-x];
            /// len - tl - x, len - tl - 2*x, ..., len - tl - dod*x
            res -= pref[x][len - tl - x];
            if(len - tl - dod*x > x) res += pref[x][len - tl - dod*x - x];
            tl += dod*x;
            bl += dod;

            dod = c/2;
            if(dod == 0) continue;
            /// tr, tr + x, ..., tr + (dod-1)*x
            res -= pref[x][tr + (dod-1)*x];
            if(tr > x) res += pref[x][tr-x];
            /// len - tr - x, len - tr - 2*x, ..., len - tr - dod*x
            res -= pref[x][len - tr - x];
            if(len - tr - dod*x > x) res += pref[x][len - tr - dod*x - x];
            tr += dod*x;
            br += dod;
        }
        for(auto c : vals) ins[c] = 0;
        sol[ind] = res;
    }
    for(int i=1; i<=qrs; i++) cout << sol[i] << "\n";
    return 0;
}

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