Submission #476422

#	Time	Username	Problem	Language	Result	Execution time	Memory
476422		neki	Diversity (CEOI21_diversity)	C++14	64 / 100	70 ms	22856 KiB

diversity

#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 500100
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007

vc<ll> a;
ll cnt[300100];
deque<ll> act;
deque<ll>::iterator poi[300100];
void add(ll i){
    if(cnt[a[i]]==0)act.push_front(a[i]), poi[a[i]]=act.begin();
    ++cnt[a[i]];
}

void rem(ll i){
    --cnt[a[i]];
    if(cnt[a[i]]==0) act.erase(poi[a[i]]);
}

ll getans(){
    ll sum=0;
    vc<ll> cs; fore(v, act) sum+=cnt[v], cs.ps(cnt[v]);
    sort(all(cs));
    
    ll ret=0;
    vc<ll> pre(2, 0);
    loop(i, 0, cs.size()){
        ret+=pre[i%2] * (sum-cs[i]-pre[i%2]);
        pre[i%2]+=cs[i];
        
        ret+=cs[i] * (sum-cs[i]);
        ret+=(cs[i] * cs[i] + cs[i])/2;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, q;cin >> n >> q;
    a.resize(n);loop(i, 0, n) cin >> a[i];
    
    vc<array<ll, 3>> que(q);
    loop(i, 0, q){ cin >> que[i][0] >> que[i][1];--que[i][0], --que[i][1];}
    loop(i, 0, q) que[i][2]=i;
    
    const ll m=550;
    sort(all(que), [&](array<ll, 3> a, array<ll, 3> b){
        if(a[0]/m==b[0]/m) return a[1]<b[1];
        return a[0]<b[0];
    });
    
    vc<ll> ans(q);
    ll l=0, r=-1;
    loop(i, 0, q){
        ll ql=que[i][0], qr=que[i][1];
        
        while(r<qr) add(++r);
        while(r>qr) rem(r--);
        
        while(l<ql) rem(l++);
        while(l>ql) add(--l);
        
        ans[que[i][2]]=getans();
    }
    
    loop(i, 0, q) cout << ans[i]<<endl;
}

Compilation message (stderr)

diversity.cpp: In function 'long long int getans()':
diversity.cpp:3:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define loop(i, a, b) for(ll i=a;i<b;++i)
......
   45 |     loop(i, 0, cs.size()){
      |          ~~~~~~~~~~~~~~~           
diversity.cpp:45:5: note: in expansion of macro 'loop'
   45 |     loop(i, 0, cs.size()){
      |     ^~~~

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