oj.uz

Submission #752642

# Submission time Handle Problem Language Result Execution time Memory
752642 2023-06-03T11:06:03 Z 이동현(#9968) Diversity (CEOI21_diversity) C++17
0 / 100
 2 ms 2816 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

const int NS = (int)3e5 + 4, TS = 150014, QS = 50004;
int n, q;
int t1[TS], t2[TS], t3[TS], t4[TS];
int a[NS];
int stkn;
int fir[NS], ed[NS], cnt[NS], pos[NS];
int B, out[QS];

struct Data{
    int l, r, id;
    Data(){}
    bool operator<(const Data&R)const{
        return (l / B < R.l / B) || (l / B == R.l / B && r < R.r);
    }
}que[QS];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    memset(ed, -1, sizeof(ed));
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for(int i = 1; i <= q; ++i){
        cin >> que[i].l >> que[i].r;
        que[i].id = i;
    }

    B = 1300;
    sort(que + 1, que + q + 1);
    int l = 1, r = 0;
    int ans = 0, szans = 0;
    auto upd = [&](int p, int v, int osz){
        --p;
        //cout << p << ' ' << v << ' ' << osz << endl;

        szans += (osz + (v > 0 ? v : 0)) * v;
        ans += (osz + (v > 0 ? v : 0)) * v;
        if(p % 2){
            int t1a = 0, t2a = 0, t3a = 0, t4a = 0;
            int t1p = 0, t2p = 0;
            for(int i = TS - 1; i > 0; i -= (i & -i)){
                t1a += t1[i], t2a += t2[i], t3a += t3[i], t4a += t4[i];
            }
            for(int i = p / 2 + 1; i > 0; i -= (i & -i)){
                t1p += t1[i], t2p += t2[i];
            }
            t1a -= osz, t1p -= osz, t2a -= osz * (p / 2), t2p -= osz * (p / 2);

            szans += v * (t3a + t1a);
            //cout << ans << ' ' << szans << ' ' << t3a << ' ' << t4a << endl;
            ans += 2 * v * t3a + (p / 2) * v * t3a + t4a * v;
            ans += v * t1a + ((p / 2) * v * t1p - t2p * v) - ((p / 2) * v * (t1a - t1p) - (t2a - t2p) * v);

            for(int i = p / 2 + 1; i < TS; i += (i & -i)){
                t1[i] += v;
                t2[i] += v * (p / 2);
            }
        }
        else{
            int t1a = 0, t2a = 0, t3a = 0, t4a = 0;
            int t3p = 0, t4p = 0;
            for(int i = TS - 1; i > 0; i -= (i & -i)){
                t1a += t1[i], t2a += t2[i], t3a += t3[i], t4a += t4[i];
            }
            for(int i = p / 2 + 1; i > 0; i -= (i & -i)){
                t3p += t3[i], t4p += t4[i];
            }
            t3a -= osz, t3p -= osz, t4a -= osz * (p / 2), t4p -= osz * (p / 2);

            //cout << "SDF" << ' ' << t1a << ' ' << t2a << ' ' << t3a << ' ' << t4a << ' ' << t3p << ' ' << t4p << endl;

            szans += v * (t1a + t3a);
            ans += 2 * v * t1a + (p / 2) * v * t1a + t2a * v;
            ans += v * t3a + ((p / 2) * v * t3p - t4p * v) - ((p / 2) * v * (t3a - t3p) - (t4a - t4p) * v);

            for(int i = p / 2 + 1; i < TS; i += (i & -i)){
                t3[i] += v;
                t4[i] += v * (p / 2);
            }
        }

        //cout << ans << ' ' << szans << endl;
    };
    auto add = [&](int val){
        if(!cnt[val]) pos[val] = ++stkn;
        int ch1 = pos[val], osz = cnt[val];
        if(cnt[val] && fir[cnt[val]] != val){
            ch1 = fir[cnt[val]];
            swap(pos[val], pos[fir[cnt[val]]]);
        }
        ++fir[cnt[val]];
        ++cnt[val];
        if(fir[cnt[val]] > ed[cnt[val]]) fir[cnt[val]] = ed[cnt[val]] = val;
        else ++ed[cnt[val]];

        upd(ch1, 1, osz);
    };
    auto del = [&](int val){
        int ch1 = pos[val], osz = cnt[val];
        if(ed[cnt[val]] != val){
            ch1 = ed[cnt[val]];
            swap(pos[val], pos[ed[cnt[val]]]);
        }
        --ed[cnt[val]];
        ++cnt[val];
        if(fir[cnt[val]] > ed[cnt[val]]) fir[cnt[val]] = ed[cnt[val]] = val;
        else --fir[cnt[val]];

        upd(ch1, -1, osz);

        if(!cnt[val]) --stkn, pos[val] = 0;
    };
    for(int i = 1; i <= q; ++i){
        while(r < que[i].r){
            ++r;
            add(a[r]);
        }
        while(l > que[i].l){
            --l;
            add(a[l]);
        }
        while(r > que[i].r){
            del(a[r]);
            --r;
        }
        while(l < que[i].l){
            del(a[l]);
            ++l;
        }

        out[que[i].id] = ans - szans * stkn + stkn * (que[i].r - que[i].l + 1) * (que[i].r - que[i].l + 2) / 2;
    }

    for(int i = 1; i <= q; ++i){
        cout << out[i] << '\n';
    }
    
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Incorrect 2 ms 2772 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Incorrect 2 ms 2772 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2816 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Incorrect 2 ms 2772 KB Output isn't correct
5 Halted 0 ms 0 KB -