oj.uz

Submission #859650

# Submission time Handle Problem Language Result Execution time Memory
859650 2023-10-10T12:12:35 Z Tenis0206 Diversity (CEOI21_diversity) C++11
4 / 100
 231 ms 460160 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];

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)
    {
        l.push_back(val);
    }
}

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]);
        }
    }
    l = aux;
    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;
        }
        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;
        }
        l.clear();
        for(int i=1;i<=nmax;i++)
        {
            nrfr[i] = 0;
            fr[i] = 0;
        }
    }
    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:42: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]
   42 |     for(int i=0; i<h.size(); i++)
      |                  ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 201812 KB Output is correct
2 Correct 22 ms 201820 KB Output is correct
3 Correct 22 ms 201812 KB Output is correct
4 Correct 23 ms 203864 KB Output is correct
5 Correct 21 ms 201812 KB Output is correct
6 Correct 22 ms 201820 KB Output is correct
7 Correct 22 ms 201812 KB Output is correct
8 Correct 22 ms 201812 KB Output is correct
9 Correct 22 ms 201808 KB Output is correct
10 Correct 23 ms 203792 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 202320 KB Output is correct
2 Correct 24 ms 207184 KB Output is correct
3 Runtime error 231 ms 460160 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 202320 KB Output is correct
2 Correct 24 ms 207184 KB Output is correct
3 Runtime error 231 ms 460160 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 202320 KB Output is correct
2 Correct 24 ms 207184 KB Output is correct
3 Runtime error 231 ms 460160 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 201812 KB Output is correct
2 Correct 22 ms 201820 KB Output is correct
3 Correct 22 ms 201812 KB Output is correct
4 Correct 23 ms 203864 KB Output is correct
5 Correct 21 ms 201812 KB Output is correct
6 Correct 22 ms 201820 KB Output is correct
7 Correct 22 ms 201812 KB Output is correct
8 Correct 22 ms 201812 KB Output is correct
9 Correct 22 ms 201808 KB Output is correct
10 Correct 23 ms 203792 KB Output is correct
11 Correct 23 ms 202320 KB Output is correct
12 Correct 24 ms 207184 KB Output is correct
13 Runtime error 231 ms 460160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 201812 KB Output is correct
2 Correct 22 ms 201820 KB Output is correct
3 Correct 22 ms 201812 KB Output is correct
4 Correct 23 ms 203864 KB Output is correct
5 Correct 21 ms 201812 KB Output is correct
6 Correct 22 ms 201820 KB Output is correct
7 Correct 22 ms 201812 KB Output is correct
8 Correct 22 ms 201812 KB Output is correct
9 Correct 22 ms 201808 KB Output is correct
10 Correct 23 ms 203792 KB Output is correct
11 Correct 23 ms 202320 KB Output is correct
12 Correct 24 ms 207184 KB Output is correct
13 Runtime error 231 ms 460160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -