이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct SegTree {
int sz;
vector<int> tree;
int ql, qr;
void merge(int i) {
tree[i] = tree[2*i]+tree[2*i+1];
}
SegTree(int N) {
sz = 1;
while (sz < N) sz *= 2;
tree.resize(2*sz);
for (int i = sz; i < sz+N; i++) tree[i] = 1;
for (int i = sz+N; i < 2*sz; i++) tree[i] = 0;
for (int i = sz-1; i >= 1; i--) merge(i);
}
int __query(int ni, int nl, int nr) {
if (qr <= nl || nr <= ql) return 0;
if (ql <= nl && nr <= qr) return tree[ni];
int nm = (nl+nr)/2;
return __query(2*ni, nl, nm) + __query(2*ni+1, nm, nr);
}
int query(int l, int r) {
ql = l;
qr = r;
return __query(1, 0, sz);
}
void set0(int i) {
i += sz;
tree[i] = 0;
for (i /= 2; i >= 1; i /= 2) {
merge(i);
}
}
};
long long count_swaps(vector<int> S) {
const int N = S.size() / 2;
vector<vector<int>> stacks(N+1); // Index where given numbers appear
vector<int> other(2*N); // Index of other pair element
for (int i = 0; i < 2*N; i++) {
const int x = abs(S[i]);
if (!stacks[x].size() || S[stacks[x].back()] == S[i]) {
stacks[x].push_back(i);
} else {
const int j = stacks[x].back();
stacks[x].pop_back();
other[i] = j;
other[j] = i;
}
}
SegTree seg(2*N);
long long ans = 0;
for (int i = 0; i < 2*N; i++) {
if (other[i] < i) continue;
if (S[i] > 0) ans++; // this is a right shoe, to be swapped at the end
ans += seg.query(i+1, other[i]);
seg.set0(i);
seg.set0(other[i]);
}
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... |