Muutokset

input/code.cpp: In function 'auto f(std::vector<int>&, int, int)':
input/code.cpp:32:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if (find_c[c] == t.size()) {

#include <bits/stdc++.h>

using namespace std;

auto f(vector<int>& inputs, int n, int m) {
    vector<long> results(m+1);
    vector<int> counts(n+1);

    vector<int> t;
    vector<int> find_a(n+1, -1), find_c(m+1, -1);

    for (int i = 0; i < m; ++i) {
        int a = inputs[i];
        if (find_a[a] == -1) {
            counts[a] = 1;
            find_a[a] = t.size();
            if (find_c[counts[a]] == -1) {
                find_c[counts[a]] = find_a[a];
            }
            t.push_back(a);
            results[i+1] = results[i] + find_a[a] + 1;
        } else {
            // viedään a oman osastonsa kärkeen; ei vaikuta hintaan
            int b = t[find_c[counts[a]]];
            swap(find_a[a], find_a[b]);
            swap(t[find_a[a]], t[find_a[b]]);

            // a siirtyy seuraavaan osastoon mutta ei liiku; ei vaikuta hintaan
            int c = counts[a];
            counts[a]++;
            find_c[c]++;
            if (find_c[c] == t.size()) {
                find_c[c] = -1;
            }
            if (find_c[counts[a]] == -1) {
                find_c[counts[a]] = find_a[a];
            }

            // Yksi a:n hinta lisää.
            results[i+1] = results[i] + find_a[a] + 1;
        }
    }
    return results;
}

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

    int n, m;
    cin >> n >> m;

    vector<int> inputs(m);
    for (int i = 0; i < m; ++i) {
        cin >> inputs[i];
        inputs[i]--;
    }
    auto results_fwd = f(inputs, n, m);
    reverse(inputs.begin(), inputs.end());
    auto results_bwd = f(inputs, n, m);
    reverse(results_bwd.begin(), results_bwd.end());

    for (int i = 1; i < m; ++i) {
        cout << results_fwd[i] + results_bwd[i] << " ";
    }
    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: ACCEPTED