Submission #1155039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155039		ace5	Diversity (CEOI21_diversity)	C++20	64 / 100	7095 ms	10116 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


const int maxn = 300005;
const int sqr = 3000;
const int pos1 = 150002;
const int maxq = 50005;

ll val[maxn];
int bl[maxn];
ll a[maxn];
int posex[maxn];
vector<pair<int,int>> ex(maxn);
int L = 0,R = -1;
int kel = 0;

struct block
{
    block(int _l,int _r,ll _sum,ll _wsum,ll _ans){l = _l,r = _r;sum = _sum;wsum = _wsum;ans = _ans;};
    block(){};
    int l,r;
    ll sum;
    ll wsum;
    ll ans;
    void upd()
    {
        sum = 0;
        wsum = 0;
        ans = 0;
        for(int j = l;j <= r;++j)
        {
            ans += val[j] * (sum * (j-l+2) - wsum) + (val[j] * (val[j] + 1) / 2);
            sum += val[j];
            wsum += (j-l+1) * val[j];
        }
    }
};

block mrg(block a,block b)
{
    block ans;
    ans.sum = a.sum + b.sum;
    ans.wsum = a.wsum + b.wsum + b.sum * (a.r-a.l+1);
    ans.ans = a.ans + b.ans + a.sum * (b.wsum + b.sum) + (a.sum * (a.r-a.l+1) - a.wsum) * b.sum;
    ans.l = a.l;
    ans.r = b.r;
    return ans;
}

block decomp[sqr];


void add_dec(int i,int x)
{
   // cout << "adding: " << x << " to " << i << endl;
    val[i] += x;
    decomp[bl[i]].upd();
   // cout << decomp[bl[i]].ans << ' ';
}

ll get(int l,int r)
{
    block ans = block(0,-1,0,0,0);
    while(l < r)
    {
        if(l % sqr != 0 || l + sqr - 1 > r)
        {
            ans = mrg(ans,block(l,l,val[l],val[l],val[l] * (val[l]+1) / 2));
            l++;
        }
        else
        {
            ans = mrg(ans,decomp[bl[l]]);
            l += sqr;
        }
    }
    return ans.ans;
}

int get_pos(int tpos,int sz)
{
    int d = (sz-tpos)/2;
    return pos1 + (sz%2 == tpos%2 ? -d : d);
}

void add(int el)
{
    //cout << el << "+\n";
    int tv = ex[posex[el]].first;
    int tpos = (upper_bound(ex.end()-kel-1,ex.end(),make_pair(tv,maxn+5))-ex.begin()-1);
    //cout << tpos << ' ';
    add_dec(get_pos(tpos,ex.size()),1);
    if(!ex[tpos].first)
        kel++;
    ex[tpos].first ++;
    int el2 = ex[tpos].second;
    swap(ex[tpos].second,ex[posex[el]].second);
    swap(posex[el],posex[el2]);
}
void sub(int el)
{
    //cout << el << "-\n";
    int tv = ex[posex[el]].first;
    int tpos = (lower_bound(ex.end()-kel-1,ex.end(),make_pair(tv,0))-ex.begin());
   // cout << tpos << ' ';
    add_dec(get_pos(tpos,ex.size()),-1);
    ex[tpos].first --;
    if(!ex[tpos].first)
        kel--;
    int el2 = ex[tpos].second;
    swap(ex[tpos].second,ex[posex[el]].second);
    swap(posex[el],posex[el2]);
}

ll res[maxq];

struct query
{
    query(int _l,int _r,int _i){l = _l;r = _r;i = _i;};
    query(){};
    int l,r,i;
    bool operator < (const query & oth){return (l/sqr != oth.l/sqr ? l/sqr < oth.l/sqr : r < oth.r);};
};

vector<query> ev;

void go_ll()
{
    L--;
    add(a[L]);
}
void go_lr()
{
    sub(a[L]);
    L++;
}
void go_rr()
{
    R++;
    add(a[R]);
}
void go_rl()
{
    sub(a[R]);
    R--;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 0;i < maxn;++i)
    {
        ex[i].second = i;
        posex[i] = i;
        val[i] = 0;
        bl[i] = i/sqr;
    }
    for(int i = 0;i < sqr;++i)
        decomp[i] = block(i*sqr,(i+1)*sqr-1,0,0,0);
    int n,q;
    cin >> n >> q;
    for(int i = 0;i < n;++i)
    {
        cin >> a[i];
    }
    for(int i = 0;i < q;++i)
    {
        int l,r;
        cin >> l >> r;
        l--;
        r--;
        ev.push_back(query(l,r,i));
    }
    sort(ev.begin(),ev.end());
    for(int i = 0;i < ev.size();++i)
    {
        int tl = ev[i].l;
        int tr = ev[i].r;
        while(L > tl)
        {
            go_ll();
        }
        while(R < tr)
        {
            go_rr();
        }
        while(L < tl)
        {
            go_lr();
        }
        while(R > tr)
        {
            go_rl();
        }
        res[ev[i].i] = get(0,maxn-1);
    }
    for(int i= 0 ;i < q;++i)
    {
        cout << res[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: 0 / 36