This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shoes.h"
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
long long count_swaps(std::vector<int> s) {
long long i = 0, j = 0, aux = 0, ans = 0, dist = 0, n = s.size() / 2;
bool viz[200100];
queue<int> lpoz[100100], rpoz[100100];
ordered_set(int) sset;
for (i = 0; i < 2*n; i++) {
if (s[i] < 0) {
lpoz[-s[i]].push(i);
}
else {
rpoz[s[i]].push(i);
}
sset.insert(i);
viz[i] = false;
}
for (i = 0; i < 2*n; i++) {
if (!viz[i]) {
if (s[i] < 0) {
lpoz[-s[i]].pop();
j = rpoz[-s[i]].front();
rpoz[-s[i]].pop();
aux = 0;
}
else {
rpoz[s[i]].pop();
j = lpoz[s[i]].front();
lpoz[s[i]].pop();
aux = 1;
}
viz[i] = viz[j] = true;
dist = sset.order_of_key(j) - sset.order_of_key(i) - 1 + aux;
ans += dist;
sset.erase(i);
sset.erase(j);
}
}
return ans;
}
# | 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... |