#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ti;
long long count_swaps(vector<int> s) {
map<int, queue<int>> mivi;
for (int i = 0; i < s.size(); i++) {
mivi[s[i]].push(i);
ti.insert(i);
}
vector<int> taken(s.size(), 0);
long long total = 0;
for (int i = 0; i < s.size(); i++) {
if (taken[i]) continue;
// cout << i << " " << total << "\n";
ti.erase(ti.find_by_order(0));
mivi[s[i]].pop();
if (s[i] < 0) {
// cout << i << " " << mivi[-s[i]].front() << '\n';
int x = ti.order_of_key(mivi[-s[i]].front());
total += x;
taken[mivi[-s[i]].front()] = 1;
ti.erase(mivi[-s[i]].front());
mivi[-s[i]].pop();
} else {
// cout << i << " " << mivi[-s[i]].front() << '\n';
int x = ti.order_of_key(mivi[-s[i]].front());
total += x + 1;
taken[mivi[-s[i]].front()] = 1;
ti.erase(mivi[-s[i]].front());
mivi[-s[i]].pop();
}
}
return total;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |