이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
struct FT {
vector<int> bit;
FT(int n): bit(n) {}
void upd(int i, int x) {
for (; i < sz(bit); i |= i+1) bit[i] += x;
}
int qry(int i) {
int ans = 0;
for (++i; i > 0; i &= i-1) ans += bit[i-1];
return ans;
}
int qry(int l, int r) {
return qry(r) - qry(l-1);
}
};
long long count_swaps(vector<int> s) {
int n = sz(s) / 2;
vector<vector<int>> left(n), right(n);
for (int i = 0; i < 2 * n; i++) {
int c = abs(s[i]) - 1;
if (s[i] < 0) {
left[c].push_back(i);
} else {
right[c].push_back(i);
}
}
vector<ar<int, 2>> a;
for (int c = 0; c < n; c++) {
for (int i = 0; i < sz(left[c]); i++) {
a.push_back({left[c][i], right[c][i]});
}
}
ll ans = 0;
for (int i = 0; i < n; i++) {
if (a[i][0] > a[i][1]) {
ans++;
swap(a[i][0], a[i][1]);
}
}
sort(a.begin(), a.end());
// cout << "here" << endl;
FT bit(2 * n);
for (int i = 0; i < n; i++) {
for (int x : a[i]) {
// cout << x << endl;
ans += bit.qry(x + 1, 2 * n - 1);
bit.upd(x, +1);
}
}
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... |