oj.uz

Submission #859630

# Submission time Handle Problem Language Result Execution time Memory
859630 2023-10-10T11:45:49 Z Tenis0206 Diversity (CEOI21_diversity) C++11
4 / 100
 46 ms 204628 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]]++;
        }
    }
}

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:59: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]
   59 |     for(int i=0; i<h.size(); i++)
      |                  ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 110168 KB Output is correct
2 Correct 15 ms 110172 KB Output is correct
3 Correct 16 ms 110172 KB Output is correct
4 Correct 14 ms 110172 KB Output is correct
5 Correct 15 ms 110484 KB Output is correct
6 Correct 14 ms 110172 KB Output is correct
7 Correct 14 ms 110172 KB Output is correct
8 Correct 22 ms 175452 KB Output is correct
9 Correct 18 ms 146812 KB Output is correct
10 Correct 19 ms 147032 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 147572 KB Output is correct
2 Correct 22 ms 152668 KB Output is correct
3 Incorrect 46 ms 204628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 147572 KB Output is correct
2 Correct 22 ms 152668 KB Output is correct
3 Incorrect 46 ms 204628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 147572 KB Output is correct
2 Correct 22 ms 152668 KB Output is correct
3 Incorrect 46 ms 204628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 110168 KB Output is correct
2 Correct 15 ms 110172 KB Output is correct
3 Correct 16 ms 110172 KB Output is correct
4 Correct 14 ms 110172 KB Output is correct
5 Correct 15 ms 110484 KB Output is correct
6 Correct 14 ms 110172 KB Output is correct
7 Correct 14 ms 110172 KB Output is correct
8 Correct 22 ms 175452 KB Output is correct
9 Correct 18 ms 146812 KB Output is correct
10 Correct 19 ms 147032 KB Output is correct
11 Correct 18 ms 147572 KB Output is correct
12 Correct 22 ms 152668 KB Output is correct
13 Incorrect 46 ms 204628 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 110168 KB Output is correct
2 Correct 15 ms 110172 KB Output is correct
3 Correct 16 ms 110172 KB Output is correct
4 Correct 14 ms 110172 KB Output is correct
5 Correct 15 ms 110484 KB Output is correct
6 Correct 14 ms 110172 KB Output is correct
7 Correct 14 ms 110172 KB Output is correct
8 Correct 22 ms 175452 KB Output is correct
9 Correct 18 ms 146812 KB Output is correct
10 Correct 19 ms 147032 KB Output is correct
11 Correct 18 ms 147572 KB Output is correct
12 Correct 22 ms 152668 KB Output is correct
13 Incorrect 46 ms 204628 KB Output isn't correct
14 Halted 0 ms 0 KB -