Submission #1049302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049302		PoonYaPat	Diversity (CEOI21_diversity)	C++14	64 / 100	185 ms	54864 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

//sl : increase from l
//sr : increase from r

const int mx=300000,MID=150000;

struct NN {
    ll sum,sl,sr,cnt;
} s[1<<22];

int ccnt[mx+5],posi[mx+5],num[mx+5];

NN merge(NN a, NN b) {
    NN res;
    res.sum=a.sum+b.sum;
    res.cnt=a.cnt+b.cnt;
    res.sl=a.sl+a.cnt*b.sum+b.sl;
    res.sr=b.sr+b.cnt*a.sum+a.sr;
    return res;
}

void update(int l, int r, int idx, int x) {
    if (x>r || x<l) return;
    if (l==r) s[idx]={ccnt[l],ccnt[l],ccnt[l],1};
    else {
        int mid=(l+r)/2;
        update(l,mid,2*idx,x);
        update(mid+1,r,2*idx+1,x);
        s[idx]=merge(s[2*idx],s[2*idx+1]);
    }
}

NN query(int l, int r, int idx, int x, int y) {
    if (x>r || y<l) return {0,0,0,0};
    if (x<=l && r<=y) return s[idx];
    int mid=(l+r)/2;
    return merge(query(l,mid,2*idx,x,y),query(mid+1,r,2*idx+1,x,y));
}

int level[mx+5],have[mx+5],idx_seq=-1; //range of box that has been used
vector<int> seq;
priority_queue<pii, vector<pii>, greater<pii>> pq[mx+5]; //(level,pos)

ll ans=0;

void sw(int a, int b) {
    swap(num[a],num[b]);
    posi[num[a]]=a;
    posi[num[b]]=b;
}

void add(int val) {

    if (!have[val]) {
        
        ++idx_seq;
        int pos=seq[idx_seq]; //the position of the seg-tree to be added
        ccnt[pos]=1;
        posi[val]=pos;
        num[pos]=val;
        update(1,mx,1,pos);
        pq[1].push(pii(level[pos],pos));
        ans+=query(1,mx,1,1,pos).sr+query(1,mx,1,pos,mx).sl-ccnt[pos];

    } else {

        int pos=posi[val], cnt=ccnt[pos]; //increase from cnt to cnt+1
        int max_pos=pq[cnt].top().second;
        sw(pos,max_pos);

        //increase from cnt to cnt+1
        pq[cnt].pop();
        pq[cnt+1].push(pii(level[max_pos],max_pos));
        ++ccnt[max_pos];
        update(1,mx,1,max_pos);
        ans+=query(1,mx,1,1,max_pos).sr+query(1,mx,1,max_pos,mx).sl-ccnt[max_pos];
    }

    ++have[val];
}

void del(int val) {

}

int n,q,a[mx+5];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ll=MID,rr=MID;
    level[MID]=0;
    seq.push_back(MID);
    for (int i=1; i<mx; ++i) {
        if (i%2==0) level[--ll]=i, seq.push_back(ll);
        else level[++rr]=i, seq.push_back(rr);
    }

    cin>>n>>q;
    for (int i=0; i<n; ++i) cin>>a[i];
    cin>>q>>q;

    for (int i=0; i<n; ++i) {
        add(a[i]);
        //cout<<"add "<<i<<" success -> "<<ans<<"\n";
    }

    cout<<ans;
}

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