Submission #1174042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174042		somefolk	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	232 ms	27976 KiB

shoes

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <complex>
#include <list>
#include <cassert>
#include <chrono>
#include <random>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define endl "\n"
#define int long long

const int INF = 1e5+7;
const int MOD = 1e9+7;

struct SGT{
    int size = 1;
    vector<int> st;

    void build(vector<int32_t> &a, int x, int lx, int rx){
        if(rx - lx == 1){
            if(lx < (int)a.size()){
                st[x] = 1;
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2*x+1, lx, m);
        build(a, 2*x+2, m, rx);
        st[x] = st[2*x+1] + st[2*x+2];
    }

    void build(int n, vector<int32_t> &a){
        while(size < n) size *= 2;
        st.resize(2*size);
        build(a, 0, 0, size);
    }

    void set(int i, int v, int x, int lx, int rx){
        if(rx - lx == 1){
            st[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m){
            set(i, v, 2*x+1, lx, m);
        } else {
            set(i, v, 2*x+2, m, rx);
        }
        st[x] = st[2*x+1] + st[2*x+2];
    }

    void set(int i, int v){
        set(i, v, 0, 0, size);
    }

    int query(int l, int r, int x, int lx, int rx){
        if(rx <= l || r <= lx) return 0;
        if(l <= lx && rx <= r) return st[x];
        int m = (lx + rx) / 2;
        int s1 = query(l, r, 2*x+1, lx, m);
        int s2 = query(l, r, 2*x+2, m, rx);
        return s1+s2;
    }

    int query(int l, int r){
        return query(l, r, 0, 0, size);
    }
};


int64_t count_swaps(vector<int32_t> a){
    int n = a.size();

    map<int, vector<int>> idx;
    for(int i = n-1; i >= 0; i--){
        idx[a[i]].push_back(i);
    }

    SGT st;
    st.build(n, a);

    int sol = 0;
    vector<bool> vis(n, false);
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            int next = idx[-a[i]].back();
            sol += st.query(min(i, next), max(i, next)) - (a[i] < 0);

            st.set(i, 0);
            vis[i] = true;
            idx[a[i]].pop_back();

            st.set(next, 0);
            vis[next] = true;
            idx[a[next]].pop_back();
        }
    }

    return sol;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15