Submission #1102295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102295		CDuong	Swap Swap Sort (CCO21_day1problem1)	C++17	0 / 25	114 ms	44356 KiB

Main

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

template<bool ALLOW_NON_PREFIX_QUERY, class T, class F, class I>
struct fenwick_tree{
    int n;
    vector<T> data;
    F TT;
    T T_id;
    I Tinv;
    fenwick_tree(F TT, T T_id, I Tinv): TT(TT), T_id(T_id), Tinv(Tinv){ }
    fenwick_tree &operator=(const fenwick_tree &fw){
        n = fw.n;
        data = fw.data;
    }
    // O(n)
    void build(int n){
        assert(n >= 0);
        this->n = n;
        data.assign(n, T_id);
    }
    // O(n)
    void build(int n, T x){
        assert(n >= 0);
        this->n = n;
        data.assign(n, x);
        for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);
    }
    // O(n)
    template<class U>
    void build(const vector<U> &a){
        n = (int)a.size();
        data.resize(n);
        copy(a.begin(), a.end(), data.begin());
        for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]);
    }
    // O(log(n))
    void update(int p, T x){
        assert(0 <= p && p < n);
        for(++ p; p <= n; p += p & -p) data[p - 1] = TT(data[p - 1], x);
    }
    // O(log(n))
    void set(int p, T x){
        update(p, TT(x, Tinv(query(p))));
    }
    // O(log(n))
    T prefix(int r) const{
        assert(0 <= r && r <= n);
        T s = T_id;
        for(; r > 0; r -= r & -r) s = TT(s, data[r - 1]);
        return s;
    }
    // O(log(n))
    T query(int l, int r) const{
        static_assert(ALLOW_NON_PREFIX_QUERY);
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return T_id;
        T sum_minus = T_id, sum_plus = T_id;
        for(; l < r; r -= r & -r) sum_plus = TT(sum_plus, data[r - 1]);
        for(; r < l; l -= l & -l) sum_minus = TT(sum_minus, data[l - 1]);
        return TT(sum_plus, Tinv(sum_minus));
    }
    // O(log(n))
    T query(int p) const{
        static_assert(ALLOW_NON_PREFIX_QUERY);
        return query(p, p + 1);
    }
    // O(log(n))
    T query_all() const{
        return prefix(n);
    }
    // pred(sum[0, r)) is T, T, ..., T, F, F, ..., F, returns max r with T
    // O(log(n))
    int max_pref(auto pred) const{
        assert(pred(T_id));
        int p = 0;
        T sum = T_id;
        for(auto i = __lg(n + 1); i >= 0; -- i) if(p + (1 << i) <= n && pred(TT(sum, data[p + (1 << i) - 1]))){
            sum = TT(sum, data[p + (1 << i) - 1]);
            p += 1 << i;
        }
        return p;
    }
    template<class output_stream>
    friend output_stream &operator<<(output_stream &out, const fenwick_tree &fw){
        out << "{";
        for(auto i = 0; i < fw.n; ++ i){
            out << fw.query(i);
            if(i != fw.n - 1) out << ", ";
        }
        return out << '}';
    }
};

template<class T, class F, class I>
auto make_fenwick_tree(F TT, T T_id, I Tinv){
    return fenwick_tree<true, T, F, I>(TT, T_id, Tinv);
}
template<class T>
auto make_fenwick_tree_sum(){
    return fenwick_tree<true, T, plus<>, negate<>>(plus<>(), T{0}, negate<>());
}
template<class T>
auto make_fenwick_tree_product(){
    auto inverse = [](const T &x){ return 1 / x; };
    return fenwick_tree<true, T, multiplies<>, decltype(inverse)>(multiplies<>(), T{1}, inverse);
}
template<class T>
auto make_fenwick_tree_min(){
    auto TT = [&](const T &x, const T &y)->T{ return min(x, y); };
    return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());
}
template<class T>
auto make_fenwick_tree_max(){
    auto TT = [&](const T &x, const T &y)->T{ return max(x, y); };
    return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>());
}

const i64 oo = 1e18;

void solve() {
    int n, k, q;
    cin >> n >> k >> q;

    vector<int> a(n), p(n);
    vector<vector<int>> pos(k);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pos[--a[i]].emplace_back(i);
    }
    iota(all(p), 0);

    vector<int> qq(q);
    vector<vector<pair<int, int>>> ntb(n);
    for (int i = 0; i < q; ++i) {
        cin >> qq[i]; --qq[i];
        ntb[p[qq[i]]].emplace_back(p[qq[i] + 1], i);
        ntb[p[qq[i] + 1]].emplace_back(p[qq[i]], ~i);
        swap(p[qq[i]], p[qq[i] + 1]);
    }

    vector<int> ap(k);
    iota(all(ap), 0);
    sort(all(ap), [&](int x, int y) {
        return isz(pos[x]) > isz(pos[y]);
    });

    auto fw = make_fenwick_tree_sum<int>();
    fw.build(n);

    vector<bool> vis(n);
    vector<i64> vis2(n, oo), change(q);
    for (auto val : ap) {
        vis[val] = true;
        for (auto idx : pos[val]) {
            fw.update(idx, 1);
        }
        for (auto [val2, qidx] : ntb[val]) if (not vis[val2]) {
            int rq = (qidx < 0 ? ~qidx : qidx);
            if (vis2[val2] != oo) {
                change[rq] = vis[val2] * (qidx < 0 ? 1 : -1);
                continue;
            }
            i64 cnt = 0;
            for (auto idx : pos[val2]) {
                cnt += fw.prefix(idx);
            }
            vis2[val2] = 1ll * isz(pos[val]) * isz(pos[val2]) - cnt * 2;
            change[rq] = vis2[val2] * (qidx < 0 ? 1 : -1);
        }
        for (auto [val2, qidx] : ntb[val]) {
            vis2[val2] = oo;
        }
        for (auto idx : pos[val]) {
            fw.update(idx, -1);
        }
    }

    i64 cres = 0;
    for (int i = k - 1; i >= 0; --i) {
        for (int j = isz(pos[i]) - 1; j >= 0; --j) {
            cres += fw.prefix(pos[i][j]);
            fw.update(pos[i][j], 1);
        }
    }
    // cout << cres << endl;

    for (int i = 0; i < q; ++i) {
        cres = cres + change[i];
        cout << cres << "\n";
    }
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Compilation message (stderr)

Main.cpp:84:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   84 |     int max_pref(auto pred) const{
      |                  ^~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 5
• Subtask 4: 0 / 14