Submission #813938

#	Time	Username	Problem	Language	Result	Execution time	Memory
813938		t6twotwo	Diversity (CEOI21_diversity)	C++17	64 / 100	7049 ms	26700 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FFOR(i,a,b,c) for(int i=(a);(c)>0?i<=(b):i>=(b);i+=(c))
#define FOOR(i,a,b) FFOR(i,a,b-1,1)
#define ROOF(i,a,b) FFOR(i,b-1,a,-1)
#define FOR(i,n) FOOR(i,0,n)
#define ROF(i,n) ROOF(i,0,n)
#define FORR(x,v) for(auto &x:v)
#define all(v) (v).begin(),(v).end()
#define lla(v) (v).rbegin(),(v).rend()
#define sz(v) (int)((v).size())
#define vc vector
#define pb push_back
#define ppb pop_back
#define bk back()
#define fr front()
#define pp pop()
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define bg begin()
#define en end()
#define em empty()
#define f first
#define s second
constexpr int T=300000,B=543;
int f[T+1],pos[T],lo[T+1],hi[T+1];
ll s;
struct node{
    ll sum,up,dw;
    int len=0;
    node(){sum=up=dw=len=0;}
    node(ll a){sum=a;up=dw=2*a;len=1;}
}st[2*T];
node operator+(const node &a, const node &b){
    node c;
    c.len=a.len+b.len;
    c.sum=a.sum+b.sum;
    c.up=a.up+b.up+b.sum*a.len;
    c.dw=b.dw+a.dw+a.sum*b.len;
    return c;
}
void update(int i,int v){
    for(i+=T,st[i]=st[i].sum+v;i/=2;){
        st[i]=st[i*2]+st[i*2+1];
    }
}
node query(int l, int r){
    node a,b;
    for(l+=T,r+=T;l<r;l/=2,r/=2){
        if(l&1) a=a+st[l++];
        if(r&1) b=st[--r]+b;
    }
    return a+b;
}
void add(int v){
    s-=1LL*f[v]*(f[v]+1)/2;
    int p=hi[f[v]];
    if(lo[f[v]]==hi[f[v]]){
        lo[f[v]]=hi[f[v]]=-1;
    }else hi[f[v]]--;
    f[v]++;
    lo[f[v]]=p;
    if(hi[f[v]]==-1){
        hi[f[v]]=p;
    }
    s+=1LL*f[v]*(f[v]+1)/2;
    update(pos[p],1);
    s+=query(0,pos[p]).dw+query(pos[p]+1,T).up;
}
void rem(int v){
    s-=1LL*f[v]*(f[v]+1)/2;
    int p=lo[f[v]];
    if(lo[f[v]]==hi[f[v]]){
        lo[f[v]]=hi[f[v]]=-1;
    }else lo[f[v]]++;
    f[v]--;
    hi[f[v]]=p;
    if(lo[f[v]]==-1){
        lo[f[v]]=p;
    }
    s+=1LL*f[v]*(f[v]+1)/2;
    update(pos[p],-1);
    s-=query(0,pos[p]).dw+query(pos[p]+1,T).up;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fill(lo,lo+T+1,-1);
    fill(hi,hi+T+1,-1);
    lo[0]=0;
    hi[0]=T-1;
    for(int i=0,l=0,r=T-1;i<T;i++){
        pos[i]=i%2==0?l++:r--;
    }
    ROOF(i,T,2*T) st[i]=0;
    ROOF(i,1,T) st[i]=st[i*2]+st[i*2+1];
    int N,Q;
    cin>>N>>Q;
    vc<int> A(N);
    FORR(x,A)cin>>x;
    vc<tuple<int,int,int,int>> query(Q);
    FOR(i,Q){
        int l,r;
        cin>>l>>r; l--;
        query[i]={l/B,-r,l,i};
    }
    sort(all(query));
    vc<ll> ans(Q);
    int L=0,R=0;
    for(auto[_,r,l,i]:query) {
        r=-r;
        while(l<L) add(A[--L]);
        while(R<r) add(A[R++]);
        while(L<l) rem(A[L++]);
        while(r<R) rem(A[--R]);
        ans[i]=s;
    }
    FORR(x,ans) cout<<x<<"\n";
    return 6/22;
}

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