Submission #1090175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090175		urd05	Diversity (CEOI21_diversity)	C++17	100 / 100	5089 ms	15888 KiB

diversity

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

int n,q;
int arr[300005];
int cnt[300005];
const int sq=1000;
typedef pair<long long,long long> P;
long long tree1[300005];
long long tree2[300005];
typedef pair<P,int> Pi;
const int MAX=300000;
long long h1,h2;

P pl(P a,P b) {
    return P(a.first+b.first,a.second+b.second);
}

P mi(P a,P b) {
    return P(a.first-b.first,a.second-b.second);
}

inline long long sum1(int i) {
    long long ret=0;
    i++;
    while (i>0) {
        ret+=tree1[i];
        i-=(i&-i);
    }
    return ret;
}

inline long long sum2(int i) {
    long long ret=0;
    i++;
    while (i>0) {
        ret+=tree2[i];
        i-=(i&-i);
    }
    return ret;
}

inline P sum3(int i) {
    i++;
    P ret=P(0,0);
    while (i>0) {
        ret.first+=tree1[i];
        ret.second+=tree2[i];
        i-=(i&-i);
    }
    return ret;
}

inline void update(int i,P val) {
    i++;
    h1+=val.first;
    h2+=val.second;
    while (i<=300004) {
        tree1[i]+=val.first;
        tree2[i]+=val.second;
        i+=(i&-i);
    }
}

int pos[300005];
int tree[300005];

inline int sum(int i) {
    i++;
    int ret=0;
    while (i>0) {
        ret+=tree[i];
        i-=(i&-i);
    }
    return ret;
}

inline void upd(int i,int val) {
    i++;
    while (i<=300004) {
        tree[i]+=val;
        i+=(i&-i);
    }
}

bool comp(Pi a,Pi b) {
    if (a.first.first/sq==b.first.first/sq) {
        return a.first.second<b.first.second;
    }
    return a.first.first/sq<b.first.first/sq;
}

long long value=0;
int chk[300005];

inline void push(int ind) {
    int now=arr[ind];
    int p=chk[cnt[now]]-1;
    p=pos[p];
    chk[cnt[now]]--;
    cnt[now]++;
    P got=sum3(p);
    long long one=got.first;
    long long two=got.second;
    value+=p*got.second-got.first;
    got=P(h1-one,h2-two);
    value+=got.first-p*got.second;
    update(p,P(p,1));
}

inline void out(int ind) {
    int now=arr[ind];
    int p=chk[cnt[now]-1];
    p=pos[p];
    chk[cnt[now]-1]++;
    cnt[now]--;
    P got=sum3(p);
    long long one=got.first;
    long long two=got.second;
    value-=p*got.second-got.first;
    got=P(h1-one,h2-two);
    value-=got.first-p*got.second;
    update(p,P(-p,-1));
}

long long ret[50005];

int main(void) {
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }
    vector<int> v;
    for(int i=1;i<=300000;i++) {
        v.push_back(i-1);
    }
    sort(v.begin(),v.end());
    vector<long long> v1;
    for(int i=0;i<v.size();i+=2) {
        v1.push_back(v[i]);
    }
    vector<long long> v2;
    for(int i=1;i<v.size();i+=2) {
        v2.push_back(v[i]);
    }
    reverse(v2.begin(),v2.end());
    for(auto x:v2) {
        v1.push_back(x);
    }
    for(int i=0;i<300000;i++) {
        pos[v1[i]]=i;
        chk[i]=300000;
    }
    upd(0,300000);
    vector<Pi> query;
    for(int i=0;i<q;i++) {
        int l,r;
        scanf("%d %d",&l,&r);
        l--;
        r--;
        ret[i]=1LL*(r-l+1)*(r-l+2)/2;
        query.push_back(Pi(P(l,r),i));
    }
    sort(query.begin(),query.end(),comp);
    int l=query[0].first.first;
    int r=query[0].first.first-1;
    for(int i=0;i<q;i++) {
        int nl=query[i].first.first;
        int nr=query[i].first.second;
        while (l>nl) {
            l--;
            push(l);
        }
        while (r<nr) {
            r++;
            push(r);
        }
        while (l<nl) {
            out(l);
            l++;
        }
        while (r>nr) {
            out(r);
            r--;
        }
        ret[query[i].second]+=value;
    }
    for(int i=0;i<q;i++) {
        printf("%lld\n",ret[i]);
    }
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i=0;i<v.size();i+=2) {
      |                 ~^~~~~~~~~
diversity.cpp:146:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for(int i=1;i<v.size();i+=2) {
      |                 ~^~~~~~~~~
diversity.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
diversity.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
diversity.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         scanf("%d %d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~

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