이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct FenwichTree {
int n;
vector<int> f;
FenwichTree(int n): n(n), f(n + 1) {}
void Modify(int pos, int value) {
for (int i = pos + 1; i <= n; i += i & -i) {
f[i] += value;
}
}
int Get(int pos) {
int result = 0;
for (int i = pos + 1; i > 0; i -= i & -i) {
result += f[i];
}
return result;
}
};
vector<int> GetShoePairs(const vector<int>& s) {
int n = static_cast<int>(s.size());
vector<int> shoe_pair(n);
map<int, int> position;
for (int i = 0; i < n; ++i) {
int shoe = s[i];
if (position.count(-shoe)) {
int pos = position[-shoe];
shoe_pair[pos] = i;
shoe_pair[i] = pos;
position.erase(-shoe);
continue;
}
position[shoe] = i;
}
return shoe_pair;
}
long long count_swaps(std::vector<int> s) {
int n = static_cast<int>(s.size());
vector<int> shoe_pair = GetShoePairs(s);
vector<int> used(n);
FenwichTree tree(n);
for (int i = 0; i < n; ++i)
tree.Modify(i, +1);
long long result = 0;
for (int i = 0; i < n; ++i) {
if (used[i])
continue;
int pr = shoe_pair[i];
int actual_pos = tree.Get(pr) - 1;
if (s[i] < 0)
result += actual_pos - 1;
else
result += actual_pos;
used[i] = used[pr] = 1;
tree.Modify(i, -1);
tree.Modify(pr, -1);
}
return result;
}
# | 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... |