Submission #926087

#	Time	Username	Problem	Language	Result	Execution time	Memory
926087		Art_ogo	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	790 ms	159856 KiB

shoes

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "shoes.h"

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
typedef pair<int, int> pii;

#define oset tree<pii,  null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>

long long count_swaps(vector<int> s) {
    int n = s.size();
    oset st;
    map<int, queue<int> > pos;
    for(int i = 0; i < n; i++){
        pos[s[i]].push(i);
        st.insert({i, s[i]});
    }
    ll res = 0;
    while(!st.empty()){
        int cur = st.begin()->se;
        int pr = pos[-cur].front();
        ll ppr = st.order_of_key({pr, -cur}) - int(cur < 0);
        res += ppr;
        pos[cur].pop();
        pos[-cur].pop();
        st.erase({pr, -cur});
        st.erase(st.begin());
    }
	return res;
}

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