oj.uz

Submission #626042

# Submission time Handle Problem Language Result Execution time Memory
626042 2022-08-11T07:21:19 Z berr Diversity (CEOI21_diversity) C++17
0 / 100
 38 ms 48084 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> freq;
set<int> s;
int val(int a, int b, int c)
{
return a*c*(a+(c-1)*b)+b*b*((((c-1)*c*(2*c-1))/6));
}



int get()
{
int k=0, n=0;
int mod=1;
set<int> cur;
int l=0, r=0, ans=0;

for(auto x: s)
{
    int i=x, j=freq[x];
    if(j==0) continue;
    cur.insert(i);
    k+=j;
    n+=(i*j);

}
for(auto x: cur)
{

    int i=x, j=freq[x];
    if(j==0) continue;

    int addleft=(j+mod)/2;
    int addright=j-addleft;

    ans+=val(l, i, addleft);
    ans+=val(n-l-i, -i, addleft);

    ans+=val(r, i, addright);
    ans+=val(n-r-i, -i, addright);

    l+=addleft*i;
    r+=addright*i;
    mod=(j+mod)%2;
}
s=cur;
return (k*n*(n+1)-n*(k-1)-ans)/2;
}



int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);

int n, q, b=550, cnt=0; cin>>n>>q;

vector<int> a(n), ans(q);
vector<array<int, 3>> query[n/b+2];


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

while(q--)
{
    int l, r; cin>>l>>r;
    l--; r--;

    query[l/b].push_back({r, l, ++cnt});
}


int l=0, r=-1;

vector<int> count(3000005);


for(int i=0; i<n/b+1; i++)
{
    sort(query[i].begin(), query[i].end());
    for(auto x: query[i])
    {
        swap(x[0], x[1]);
        while(x[0]>l)
        {
            count[a[l]]--;
            if(count[a[l]]!=0)
            freq[count[a[l]]]++;
            freq[count[a[l]]+1]--;
            if(freq[count[a[l]]]==1&&count[a[l]]!=0) s.insert(count[a[l]]);
            l++;
        }
        while(x[0]<l)
        {
            l--;
            count[a[l]]++;
            freq[count[a[l]]]++;
            if(freq[count[a[l]]-1]>0)
            freq[count[a[l]]-1]--;
            if(freq[count[a[l]]]==1&&count[a[l]]!=0) s.insert(count[a[l]]);

        }
        while(x[1]<r)
        {
            if(count[a[r]]!=0)
            freq[count[a[r]]]--;
            count[a[r]]--;
            freq[count[a[r]]]++;
            if(freq[count[a[r]]]==1&&count[a[r]]!=0) s.insert(count[a[r]]);
            r--;
        }

        while(x[1]>r)
        {
            r++;
            if(count[a[r]]!=0)
            freq[count[a[r]]]--;
            count[a[r]]++;
            freq[count[a[r]]]++;
            if(freq[count[a[r]]]==1&&count[a[r]]!=0) s.insert(count[a[r]]);

        }


        ans[x[2]-1]=get();
    }
}



for(int i=0; i<ans.size(); i++) cout<<ans[i]<<"\n";

}

Compilation message

diversity.cpp: In function 'int32_t main()':
diversity.cpp:133:15: 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]
  133 | for(int i=0; i<ans.size(); i++) cout<<ans[i]<<"\n";
      |              ~^~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 48084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 47988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 47988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 47988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 48084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 48084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -