Submission #697551

#	Time	Username	Problem	Language	Result	Execution time	Memory
697551		piOOE	Diversity (CEOI21_diversity)	C++17	100 / 100	6621 ms	14796 KiB

diversity

#pragma GCC optimize("O3, unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct SmartFenwick {
    vector<ll> k, b;
    int n{};
    ll S = 0, Sum = 0;

    void init(int x) {
        n = x;
        k.resize(x + 1), b.resize(x + 1);
    }

    inline void add(int i, ll v, ll vv) {
        for (int x = i + 1; x <= n; x += x & -x) {
            k[x] += v;
            b[x] += vv;
        }
    }

    inline void rangeAdd(int l, int r, ll v) {
        Sum += (r - l) * v;
        if (l == 0) {
            S += v;
            add(r, -v, (r - 1) * v);
        } else {
            add(l, v, (l - 1) * -v);
        }
    }

    inline ll sum(int i) {
        ll K = 0, B = 0;

        for (int x = i + 1; x > 0; x -= x & -x) {
            K += k[x], B += b[x];
        }

        return B + K * i;
    }

    inline ll rangeSum(int l, int r) {
        return sum(r - 1) - sum(l - 1) + (r - l) * S;
    }
} t[2][2]; // (left/right), (L/R)

struct Query {
    int l, r, block, idx;

    bool operator<(Query oth) const {
        if (oth.block != block) {
            return block < oth.block;
        }

        return (block & 1) ? r > oth.r : r < oth.r;
    }
};

constexpr int B = 1400;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> yy = a;
    sort(yy.begin(), yy.end());
    yy.resize(unique(yy.begin(), yy.end()) - yy.begin());

    for (int &x : a) {
        x = lower_bound(yy.begin(), yy.end(), x) - yy.begin();
    }

    const int m = yy.size();

    vector<Query> queries(q);
    vector<ll> answer(q);

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l -= 1;

        queries[i].l = l, queries[i].r = r, queries[i].block = l / B, queries[i].idx = i;
    }

    sort(queries.begin(), queries.end());

    vector<int> head(n + 1);

    for (int i = 1; i <= n; ++i) {
        head[i] = m;
    }

    vector<int> pos(m), cnt(m), ord(m);
    iota(pos.begin(), pos.end(), 0);
    ord = pos;

    int siz[2]{(m + 1) / 2, m / 2};

    t[0][0].init(siz[0]);
    t[0][1].init(siz[0]);
    t[1][0].init(siz[1]);
    t[1][1].init(siz[1]);

    ll ans = 0;

    int len = 0;

    auto eval = [&](int i) {
        return 1LL * cnt[i] * (len - cnt[i]) + 1LL * (cnt[i] + 1) * cnt[i] / 2;
    };

    auto modify = [&](int i, int x) {
        ans += x * len;

        len += x;

        ans -= eval(i);

        int p = pos[i];
        int start = (x == -1 ? head[cnt[i]] : head[cnt[i] + 1] - 1);

        if (p != start) {
            int id = ord[start];
            pos[id] = p;
            ord[p] = id;
            pos[i] = start;
            ord[start] = i;
            p = start;
        }

        int side = p % 2;
        int s = p / 2;

        ans += x * t[side][side ^ 1].rangeSum(s + 1, siz[side]);
        t[side][side].rangeAdd(s + 1, siz[side], x);

        t[side][side ^ 1].rangeAdd(0, s, x);
        ans += x * t[side][side].rangeSum(0, s);

        ans += x * t[side ^ 1][side ^ 1].Sum;
        t[side ^ 1][side].S += x;
        t[side ^ 1][side].Sum += x * siz[side ^ 1];

        if (x == -1) {
            head[cnt[i]] = p + 1;
            cnt[i] -= 1;
        } else {
            cnt[i] += 1;
            head[cnt[i]] = p;
        }

        ans += eval(i);
    };

    int lx = 0, rx = 0;

    for (auto [l, r, bl, i] : queries) {
        while (rx < r) {
            modify(a[rx++], 1);
        }

        while (lx > l) {
            modify(a[--lx], 1);
        }

        while (lx < l) {
            modify(a[lx++], -1);
        }

        while (rx > r) {
            modify(a[--rx], -1);
        }

        answer[i] = ans;
    }

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

    return 0;
}

Compilation message (stderr)

diversity.cpp:1:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops")
      |                                        ^
diversity.cpp:13:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   13 |     void init(int x) {
      |                    ^
diversity.cpp:18:39: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   18 |     inline void add(int i, ll v, ll vv) {
      |                                       ^
diversity.cpp:25:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   25 |     inline void rangeAdd(int l, int r, ll v) {
      |                                            ^
diversity.cpp:35:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   35 |     inline ll sum(int i) {
      |                        ^
diversity.cpp:45:36: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   45 |     inline ll rangeSum(int l, int r) {
      |                                    ^
diversity.cpp:53:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   53 |     bool operator<(Query oth) const {
      |                               ^~~~~
diversity.cpp:64:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   64 | int main() {
      |          ^
diversity.cpp: In function 'int main()':
diversity.cpp:121:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  121 |     auto eval = [&](int i) {
      |                          ^
diversity.cpp:125:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  125 |     auto modify = [&](int i, int x) {
      |                                   ^

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36