oj.uz

Submission #859624

# Submission time Handle Problem Language Result Execution time Memory
859624 2023-10-10T11:40:21 Z Tenis0206 Diversity (CEOI21_diversity) C++11
4 / 100
 46 ms 254032 KB 
#include <bits/stdc++.h>

using namespace std;

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

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;

long long 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(i);
        }
        else
        {
            nrfr[fr[i]]++;
        }
    }
}

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

long long 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;
    }
    long long 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;
}

long long solve_light(int x, int y)
{
    long long 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;
}

long long 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];
    }
    long long 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];
            }
        }
    }
}

int 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(int, int)':
diversity.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0; i<h.size(); i++)
      |                  ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 206672 KB Output is correct
2 Correct 23 ms 206676 KB Output is correct
3 Correct 22 ms 206648 KB Output is correct
4 Correct 23 ms 206736 KB Output is correct
5 Correct 22 ms 206684 KB Output is correct
6 Correct 23 ms 206684 KB Output is correct
7 Correct 23 ms 206684 KB Output is correct
8 Correct 24 ms 206684 KB Output is correct
9 Correct 23 ms 206684 KB Output is correct
10 Correct 23 ms 206692 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 206940 KB Output is correct
2 Correct 25 ms 211244 KB Output is correct
3 Incorrect 46 ms 254032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 206940 KB Output is correct
2 Correct 25 ms 211244 KB Output is correct
3 Incorrect 46 ms 254032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 206940 KB Output is correct
2 Correct 25 ms 211244 KB Output is correct
3 Incorrect 46 ms 254032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 206672 KB Output is correct
2 Correct 23 ms 206676 KB Output is correct
3 Correct 22 ms 206648 KB Output is correct
4 Correct 23 ms 206736 KB Output is correct
5 Correct 22 ms 206684 KB Output is correct
6 Correct 23 ms 206684 KB Output is correct
7 Correct 23 ms 206684 KB Output is correct
8 Correct 24 ms 206684 KB Output is correct
9 Correct 23 ms 206684 KB Output is correct
10 Correct 23 ms 206692 KB Output is correct
11 Correct 23 ms 206940 KB Output is correct
12 Correct 25 ms 211244 KB Output is correct
13 Incorrect 46 ms 254032 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 206672 KB Output is correct
2 Correct 23 ms 206676 KB Output is correct
3 Correct 22 ms 206648 KB Output is correct
4 Correct 23 ms 206736 KB Output is correct
5 Correct 22 ms 206684 KB Output is correct
6 Correct 23 ms 206684 KB Output is correct
7 Correct 23 ms 206684 KB Output is correct
8 Correct 24 ms 206684 KB Output is correct
9 Correct 23 ms 206684 KB Output is correct
10 Correct 23 ms 206692 KB Output is correct
11 Correct 23 ms 206940 KB Output is correct
12 Correct 25 ms 211244 KB Output is correct
13 Incorrect 46 ms 254032 KB Output isn't correct
14 Halted 0 ms 0 KB -