이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n;
ll ft[N];
unordered_map<int, queue<int>> q;
void update(int x, ll val) {
for(; x <= n+5; x+=x&(-x)) ft[x]+=val;
}
ll query(int x) {
ll ret = 0;
for(; x > 0; x-=x&(-x)) ret+=ft[x];
return ret;
}
ll count_swaps(vector<int> a) {
n = a.size();
memset(ft, 0, sizeof ft);
ll ans = 0;
for(int i = 0; i < n; i++) {
bool right = a[i] > 0;
if(i > 0 && !q[-a[i]].empty()) {
int x = q[-a[i]].front(); q[-a[i]].pop();
ans += query(i+1)-query(x+1);
if(!right) ans++;
update(x+1, 1);
update(i+2, -1);
} else {
q[a[i]].push(i);
}
update(i+1, 1);
}
q.clear();
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... |