이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 2e6+10;
bool vis[mxN];
int st[mxN];
int n;
void upd(int idx, int x) {
st[idx += n] = x;
for(idx >>= 1; idx >= 1; idx >>= 1) st[idx] = st[idx*2] + st[idx*2+1];
}
int query(int l, int r) {
++r;
int ans = 0;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) ans += st[l++];
if(r & 1) ans += st[--r];
}
return ans;
}
ll count_swaps(vector<int> v) {
n = v.size();
ll ans = 0;
multiset<array<int, 2>> m;
for(int i = 0; i < n; i++) {
m.insert({v[i], i});
}
for(int i = 0; i < n; i++) {
if(vis[i]) continue;
auto it = m.lower_bound({-v[i], -1});
int idx = (*it)[1];
int mn = query(i+1, idx-1);
vis[i] = vis[idx] = true;
m.erase(it);
m.erase({v[i], i});
if(v[i] > 0) {
ans += (idx-i)-mn;
}
else {
ans += (idx-i-1)-mn;
}
upd(i, 1);
upd(idx, 1);
}
return ans;
}
/*
int main()
{
ll ans = count_swaps({2, 1, -1, -2});
cout << 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... |