Muutokset

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

constexpr auto MAX = 100001;
static __gnu_pbds::tree<std::pair<int, int>,
                        __gnu_pbds::null_type,
                        std::greater<std::pair<int, int>>,
                        __gnu_pbds::rb_tree_tag,
                        __gnu_pbds::tree_order_statistics_node_update> S;
static std::vector<int> C1(MAX), C2(MAX), R1(MAX), R2(MAX);

static int count(int c) {
    return std::distance(S.lower_bound({c, MAX}), S.upper_bound({c, -1}));
}

static int order(int c) {
    return S.order_of_key({c, MAX});
}

int main() {
    int n, m, i = 0;
    std::cin >> n >> m;
    std::vector<int> M(m);
    for (auto& x : M) {
        std::cin >> x;
        auto& c = C1[x];
        S.erase({c, x});
        ++c;
        S.insert({c, x});
        R1[i] = (i > 0 ? R1[i - 1] : 0) + order(c) + count(c);
        ++i;
    }
    S.clear();
    for (auto it = M.rbegin(); it != M.rend(); ++it) {
        --i;
        const auto x = *it;
        auto& c = C2[x];
        S.erase({c, x});
        ++c;
        S.insert({c, x});
        R2[i] = (i != m - 1 ? R2[i + 1] : 0) + order(c) + count(c);
    }
    for (auto j = 1; j < m; ++j) {
        std::cout << R1[j - 1] + R2[j] << ' ';
    }
    std::cout << '\n';
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED