Muutokset

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

using Z = long long int;

vector<Z> laskeAlkuosaHinnat(Z n, const vector<Z>& haut) {
    Z m = haut.size();
    vector<Z> ret(m + 1);

    // lkm[i] = montako hakua luvulle i
    vector<Z> lkm(n);

    // lkm2[i] = monellako j pätee lkm[j] = i
    vector<Z> lkm2(m + 1);
    lkm2[0] = n;

    for(Z hi = 0; hi < m; ++hi) {
        Z haku = haut[hi];
        --lkm2[lkm[haku]];
        ++lkm[haku];
        ++lkm2[lkm[haku]];

        Z v = 0;
        Z p = 1;
        for(Z i = m; i >= 0; --i) {
            for(Z j = 0; j < lkm2[i]; ++j) {
                v += p * i;
                ++p;
            }
        }
        ret[hi + 1] = v;
    }

    return ret;
}

int main() {
    Z n, m;
    cin >> n >> m;

    vector<Z> haut(m);
    for(Z& haku : haut) {
        cin >> haku;
        --haku;
    }

    vector<Z> alkuosaHinnat = laskeAlkuosaHinnat(n, haut);
    reverse(haut.begin(), haut.end());
    vector<Z> loppuosaHinnat = laskeAlkuosaHinnat(n, haut);

    for(Z i = 1; i < m; ++i) {
        cout << alkuosaHinnat[i] + loppuosaHinnat[m - i] << " ";
    }
    cout << "\n";

    return 0;
}

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: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED