oj.uz

Submission #859625

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

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

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 24 ms 208216 KB Output is correct
2 Correct 23 ms 208208 KB Output is correct
3 Correct 23 ms 208220 KB Output is correct
4 Correct 23 ms 208252 KB Output is correct
5 Correct 24 ms 208216 KB Output is correct
6 Correct 25 ms 208468 KB Output is correct
7 Correct 24 ms 208208 KB Output is correct
8 Correct 23 ms 208416 KB Output is correct
9 Correct 23 ms 208212 KB Output is correct
10 Correct 23 ms 208208 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 208732 KB Output is correct
2 Correct 28 ms 213084 KB Output is correct
3 Incorrect 46 ms 255824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 208732 KB Output is correct
2 Correct 28 ms 213084 KB Output is correct
3 Incorrect 46 ms 255824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 208732 KB Output is correct
2 Correct 28 ms 213084 KB Output is correct
3 Incorrect 46 ms 255824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 208216 KB Output is correct
2 Correct 23 ms 208208 KB Output is correct
3 Correct 23 ms 208220 KB Output is correct
4 Correct 23 ms 208252 KB Output is correct
5 Correct 24 ms 208216 KB Output is correct
6 Correct 25 ms 208468 KB Output is correct
7 Correct 24 ms 208208 KB Output is correct
8 Correct 23 ms 208416 KB Output is correct
9 Correct 23 ms 208212 KB Output is correct
10 Correct 23 ms 208208 KB Output is correct
11 Correct 26 ms 208732 KB Output is correct
12 Correct 28 ms 213084 KB Output is correct
13 Incorrect 46 ms 255824 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 208216 KB Output is correct
2 Correct 23 ms 208208 KB Output is correct
3 Correct 23 ms 208220 KB Output is correct
4 Correct 23 ms 208252 KB Output is correct
5 Correct 24 ms 208216 KB Output is correct
6 Correct 25 ms 208468 KB Output is correct
7 Correct 24 ms 208208 KB Output is correct
8 Correct 23 ms 208416 KB Output is correct
9 Correct 23 ms 208212 KB Output is correct
10 Correct 23 ms 208208 KB Output is correct
11 Correct 26 ms 208732 KB Output is correct
12 Correct 28 ms 213084 KB Output is correct
13 Incorrect 46 ms 255824 KB Output isn't correct
14 Halted 0 ms 0 KB -