Submission #384951

#	Time	Username	Problem	Language	Result	Execution time	Memory
384951		timmyfeng	Group Photo (JOI21_ho_t3)	C++17	100 / 100	365 ms	492 KiB

Main

#include <bits/stdc++.h>
using namespace std;

template <class T>
struct fenwick {
    vector<T> tree;
    int n;

    fenwick(int n) : n(n) {
        tree.resize(n + 1);
    }

    void update(int a, T x) {
        for ( ; a <= n; a += (a & -a)) {
            tree[a] += x;
        }
    }

    T query(int a) {
        T res = 0;
        for ( ; a > 0; a -= (a & -a)) {
            res += tree[a];
        }
        return res;
    }

    int lower_bound(T k) {
        int res = 0;
        T sum = 0;
        for (int i = __lg(n); i >= 0; --i) {
            if (res + (1 << i) <= n && sum + tree[res + (1 << i)] < k) {
                res += 1 << i;
                sum += tree[res];
            }
        }
        return res + 1;
    }
};

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

    int n;
    cin >> n;

    vector<int> perm(n), where(n);
    for (int i = 0; i < n; ++i) {
        cin >> perm[i];
        where[--perm[i]] = i;
    }

    vector<int> ans(n + 1, n * n);
    ans[0] = 0;

    for (int i = 0; i < n; ++i) {
        int segment = 0;
        fenwick<int> sum(n);
        for (int j = 0; i + j < n; ++j) {
            segment += where[i + j] - j + sum.query(where[i + j]);
            ans[i + j + 1] = min(ans[i + j + 1], ans[i] + segment);
            sum.update(where[i + j] + 1, 1);
        }

        for (int j = i + 1; j < n; ++j) {
            where[j] -= where[j] > where[i];
        }
    }

    cout << ans[n] << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36