oj.uz

Submission #859632

# Submission time Handle Problem Language Result Execution time Memory
859632 2023-10-10T11:47:50 Z Tenis0206 Diversity (CEOI21_diversity) C++11
4 / 100
 47 ms 232284 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 3e5;
const int c = 800;

int n,q;
int v[nmax + 5];

int fr[nmax + 5];

int nrfr[nmax + 5];

int st[nmax + 5], dr[nmax + 5];

vector<int> h;

int sp[c + 5][nmax + 5];

void get_fr(int st, int dr)
{
    for(int j=1; j<=nmax; j++)
    {
        fr[j] = 0;
        nrfr[j] = 0;
    }
    h.clear();
    for(int i=st; i<=dr; i++)
    {
        ++fr[v[i]];
    }
    for(int i=1; i<=nmax; i++)
    {
        if(fr[i] > c)
        {
            h.push_back(fr[i]);
        }
        else
        {
            nrfr[fr[i]]++;
        }
    }
    sort(h.begin(),h.end(),greater<int>());
}

int sum_prod(int p, int st, int dr)
{
    if(st - p <= 0)
    {
        return sp[p][dr];
    }
    return sp[p][dr] - sp[p][st - p];
}

int solve_heavy(int x, int y)
{
    deque<int> d;
    for(int i=0; i<h.size(); i++)
    {
        if(i % 2 == 0)
        {
            d.push_back(h[i]);
        }
        else
        {
            d.push_front(h[i]);
        }
    }
    int sum_st = 0, sum_dr = 0;
    for(int i=1; i<=c; i++)
    {
        sum_st += st[i] * i;
        sum_dr += dr[i] * i;
    }
    for(auto it : d)
    {
        sum_dr += it;
    }
    int rez = 0;
    for(auto it : d)
    {
        sum_dr -= it;
        rez += 1LL * (y - x + 1) * (y - x + 2) / 2;
        rez -= 1LL * sum_st * (sum_st + 1) / 2;
        rez -= 1LL * sum_dr * (sum_dr + 1) / 2;
        sum_st += it;
    }
    return rez;
}

int solve_light(int x, int y)
{
    int rez = 0;

    int sum_dr = 0, sum_st = 0;
    for(int i=1; i<=c; i++)
    {
        sum_dr += dr[i] * i;
        sum_dr += st[i] * i;
    }
    for(auto it : h)
    {
        sum_dr += it;
    }
    for(int i=1; i<=c; i++)
    {
        int cnt = st[i];
        rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt;
        rez -= sum_prod(i, sum_st, sum_st + i * (cnt - 1));
        rez -= sum_prod(i, sum_dr - i * cnt, sum_dr - i);
        sum_st += st[i] * i;
        sum_dr -= st[i] * i;
    }

    sum_dr = 0, sum_st = 0;
    for(int i=1; i<=c; i++)
    {
        sum_st += st[i] * i;
        sum_st += dr[i] * i;
    }
    for(auto it : h)
    {
        sum_st += it;
    }
    for(int i=1; i<=c; i++)
    {
        int cnt = dr[i];
        rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt;
        rez -= sum_prod(i, sum_st - i * cnt, sum_st - i);
        rez -= sum_prod(i, sum_dr, sum_dr + i * (cnt - 1));
        sum_st -= dr[i] * i;
        sum_dr += dr[i] * i;
    }

    return rez;
}

int query(int x, int y)
{
    int nr = h.size();
    for(int i=1; i<=c; i++)
    {
        if(nrfr[i]==0)
        {
            st[i] = dr[i] = 0;
            continue;
        }
        if(nrfr[i] % 2 == 0)
        {
            st[i] = dr[i] = nrfr[i] / 2;
        }
        else
        {
            if(nr % 2 == 0)
            {
                st[i] = nrfr[i] / 2;
                dr[i] = nrfr[i] / 2 + 1;
            }
            else
            {
                st[i] = nrfr[i] / 2 + 1;
                dr[i] = nrfr[i] / 2;
            }
        }
        nr += nrfr[i];
    }
    int rez = 0;
    rez += solve_heavy(x,y);
    rez += solve_light(x,y);
    return rez;
}

void precalc()
{
    for(int p=1; p<=c; p++)
    {
        for(int i=1; i<=n; i++)
        {
            sp[p][i] = 1LL * i * (i + 1) / 2;
            if(i - p > 0)
            {
                sp[p][i] += sp[p][i - p];
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    precalc();
    for(int i=1; i<=q; i++)
    {
        /*query x;
        cin>>x.st>>x.dr;
        x.poz = i;
        int bucket = get_bucket(x.st);
        B[bucket].push_back(x);
        */
        int st,dr;
        cin>>st>>dr;
        get_fr(st,dr);
        cout<<query(st,dr)<<'\n';
    }
    return 0;
}

Compilation message

diversity.cpp: In function 'long long int solve_heavy(long long int, long long int)':
diversity.cpp:60:19: 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]
   60 |     for(int i=0; i<h.size(); i++)
      |                  ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 175452 KB Output is correct
2 Correct 20 ms 175636 KB Output is correct
3 Correct 20 ms 175452 KB Output is correct
4 Correct 20 ms 175524 KB Output is correct
5 Correct 21 ms 175452 KB Output is correct
6 Correct 21 ms 175644 KB Output is correct
7 Correct 21 ms 175452 KB Output is correct
8 Correct 20 ms 175448 KB Output is correct
9 Correct 21 ms 175708 KB Output is correct
10 Correct 20 ms 175452 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 175964 KB Output is correct
2 Correct 23 ms 181176 KB Output is correct
3 Incorrect 47 ms 232284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 175964 KB Output is correct
2 Correct 23 ms 181176 KB Output is correct
3 Incorrect 47 ms 232284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 175964 KB Output is correct
2 Correct 23 ms 181176 KB Output is correct
3 Incorrect 47 ms 232284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 175452 KB Output is correct
2 Correct 20 ms 175636 KB Output is correct
3 Correct 20 ms 175452 KB Output is correct
4 Correct 20 ms 175524 KB Output is correct
5 Correct 21 ms 175452 KB Output is correct
6 Correct 21 ms 175644 KB Output is correct
7 Correct 21 ms 175452 KB Output is correct
8 Correct 20 ms 175448 KB Output is correct
9 Correct 21 ms 175708 KB Output is correct
10 Correct 20 ms 175452 KB Output is correct
11 Correct 20 ms 175964 KB Output is correct
12 Correct 23 ms 181176 KB Output is correct
13 Incorrect 47 ms 232284 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 175452 KB Output is correct
2 Correct 20 ms 175636 KB Output is correct
3 Correct 20 ms 175452 KB Output is correct
4 Correct 20 ms 175524 KB Output is correct
5 Correct 21 ms 175452 KB Output is correct
6 Correct 21 ms 175644 KB Output is correct
7 Correct 21 ms 175452 KB Output is correct
8 Correct 20 ms 175448 KB Output is correct
9 Correct 21 ms 175708 KB Output is correct
10 Correct 20 ms 175452 KB Output is correct
11 Correct 20 ms 175964 KB Output is correct
12 Correct 23 ms 181176 KB Output is correct
13 Incorrect 47 ms 232284 KB Output isn't correct
14 Halted 0 ms 0 KB -