oj.uz

Submission #859656

# Submission time Handle Problem Language Result Execution time Memory
859656 2023-10-10T12:18:53 Z Tenis0206 Diversity (CEOI21_diversity) C++11
4 / 100
 63 ms 320356 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

struct qry
{
    int st, dr, poz;
};

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

int fr[nmax + 5];

int nrfr[nmax + 5];

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

vector<int> l, h;

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

vector<qry> B[bsize + 5];

bool sel[nmax + 5];

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 Add(int val)
{
    --nrfr[fr[val]];
    ++fr[val];
    ++nrfr[fr[val]];
    if(fr[val] == c + 1 && !sel[val])
    {
        l.push_back(val);
        sel[val] = true;
    }
}

void Remove(int val)
{
    --nrfr[fr[val]];
    --fr[val];
    ++nrfr[fr[val]];
}

void build_h()
{
    vector<int> aux;
    h.clear();
    for(auto it : l)
    {
        if(fr[it] > c)
        {
            aux.push_back(it);
            h.push_back(fr[it]);
        }
    }
    for(auto it : l)
    {
        sel[it] = false;
    }
    l = aux;
    for(auto it : l)
    {
        sel[it] = true;
    }
    sort(h.begin(),h.end(),greater<int>());
}

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 get_bucket(int poz)
{
    return (poz - 1) / bsize + 1;
}

bool cmp(qry a, qry b)
{
    return (a.dr < b.dr);
}

int rez[nmax + 5];

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++)
    {
        qry x;
        cin>>x.st>>x.dr;
        x.poz = i;
        int bucket = get_bucket(x.st);
        B[bucket].push_back(x);
    }
    for(int b=1;b<=bsize+1;b++)
    {
        if(!B[b].size())
        {
            continue;
        }
        nrfr[0] = n;
        l.clear();
        for(int i=1;i<=nmax;i++)
        {
            nrfr[i] = 0;
            fr[i] = 0;
            sel[i] = false;
        }
        sort(B[b].begin(), B[b].end(),cmp);
        int last_st = B[b].front().st, last_dr = B[b].front().st - 1;
        for(auto it : B[b])
        {
            int st = it.st;
            int dr = it.dr;
            int poz = it.poz;
            for(int i=last_dr+1;i<=dr;i++)
            {
                Add(v[i]);
            }
            if(last_st < st)
            {
                for(int i=last_st;i<st;i++)
                {
                    Remove(v[i]);
                }
            }
            else
            {
                for(int i=st;i<last_st;i++)
                {
                    Add(v[i]);
                }
            }
            build_h();
            rez[poz] = query(st,dr);
            last_st = st, last_dr = dr;
        }
    }
    for(int i=1;i<=q;i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 176884 KB Output is correct
2 Correct 25 ms 226128 KB Output is correct
3 Correct 25 ms 242260 KB Output is correct
4 Correct 25 ms 242256 KB Output is correct
5 Correct 29 ms 279132 KB Output is correct
6 Correct 28 ms 266844 KB Output is correct
7 Correct 27 ms 262744 KB Output is correct
8 Correct 28 ms 262736 KB Output is correct
9 Correct 30 ms 262736 KB Output is correct
10 Correct 28 ms 264796 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 269440 KB Output is correct
2 Correct 34 ms 272220 KB Output is correct
3 Incorrect 63 ms 320356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 269440 KB Output is correct
2 Correct 34 ms 272220 KB Output is correct
3 Incorrect 63 ms 320356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 269440 KB Output is correct
2 Correct 34 ms 272220 KB Output is correct
3 Incorrect 63 ms 320356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 176884 KB Output is correct
2 Correct 25 ms 226128 KB Output is correct
3 Correct 25 ms 242260 KB Output is correct
4 Correct 25 ms 242256 KB Output is correct
5 Correct 29 ms 279132 KB Output is correct
6 Correct 28 ms 266844 KB Output is correct
7 Correct 27 ms 262744 KB Output is correct
8 Correct 28 ms 262736 KB Output is correct
9 Correct 30 ms 262736 KB Output is correct
10 Correct 28 ms 264796 KB Output is correct
11 Correct 30 ms 269440 KB Output is correct
12 Correct 34 ms 272220 KB Output is correct
13 Incorrect 63 ms 320356 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 176884 KB Output is correct
2 Correct 25 ms 226128 KB Output is correct
3 Correct 25 ms 242260 KB Output is correct
4 Correct 25 ms 242256 KB Output is correct
5 Correct 29 ms 279132 KB Output is correct
6 Correct 28 ms 266844 KB Output is correct
7 Correct 27 ms 262744 KB Output is correct
8 Correct 28 ms 262736 KB Output is correct
9 Correct 30 ms 262736 KB Output is correct
10 Correct 28 ms 264796 KB Output is correct
11 Correct 30 ms 269440 KB Output is correct
12 Correct 34 ms 272220 KB Output is correct
13 Incorrect 63 ms 320356 KB Output isn't correct
14 Halted 0 ms 0 KB -