이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
class FenwickTree {
private:
int sz;
vector <int> v;
int lsb(int x) {
return (x & (-x));
}
public:
FenwickTree(int n) {
sz = n;
v.resize(sz + 1);
}
void update(int poz) {
for (int i = poz; i <= sz; i += lsb(i)) {
v[i]++;
}
}
int query(int poz) {
int ans = 0;
for (int i = poz; i; i -= lsb(i)) {
ans += v[i];
}
return ans;
}
};
int n;
long long computeInversions(vector <int> v) {
long long inv = 0;
FenwickTree aib(2 * n);
for (int i = 2 * n - 1; i >= 0; i--) {
inv += aib.query(v[i]);
aib.update(v[i] + 1);
}
return inv;
}
long long count_swaps(vector<int> s) {
n = (int) s.size() / 2;
vector <int> v(2 * n), ord;
vector <queue <int>> q(2 * n);
int p = 0;
for (int i = 0; i < 2 * n; i++) {
if (s[i] > 0) {
if (!q[n + s[i]].empty()) {
int poz = q[n + s[i]].front();
q[n + s[i]].pop();
v[poz] = p;
v[i] = p + 1;
p += 2;
}
else {
q[s[i]].push(i);
}
}
else {
if (!q[-s[i]].empty()) {
int poz = q[-s[i]].front();
q[-s[i]].pop();
v[poz] = p + 1;
v[i] = p;
p += 2;
}
else {
q[n - s[i]].push(i);
}
}
}
return computeInversions(v);
}
# | 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... |