Submission #384949

#	Time	Username	Problem	Language	Result	Execution time	Memory
384949		timmyfeng	Group Photo (JOI21_ho_t3)	C++17	100 / 100	3102 ms	748 KiB

Main

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

#include <bits/extc++.h>

template <class T, class Comp = less<T>>
using ordered_set = __gnu_pbds::tree<
    T, __gnu_pbds::null_type, Comp,
    __gnu_pbds::rb_tree_tag,
    __gnu_pbds::tree_order_statistics_node_update
>;

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;
        ordered_set<int> indices;
        for (int j = 0; i + j < n; ++j) {
            segment += where[i + j] - j + indices.order_of_key(where[i + j]);
            ans[i + j + 1] = min(ans[i + j + 1], ans[i] + segment);
            indices.insert(where[i + j]);
        }

        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