이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+45;
ll n,a[N];
ll drvo[10*N];
bool gotov[2*N];
void build(int i,int j,int node){
if(i == j){
drvo[node] = 1;
return;
}
int mid = i+(j-i)/2;
build(i,mid,2*node);
build(mid+1,j,2*node+1);
drvo[node] = drvo[2*node]+drvo[2*node+1];
}
void update(int i,int j,int pos,int node){
if(i == j){
drvo[node] = 0;
return;
}
int mid = i+(j-i)/2;
if(pos <= mid){
update(i,mid,pos,2*node);
}
else{
update(mid+1,j,pos,2*node+1);
}
drvo[node] = drvo[2*node]+drvo[2*node+1];
}
ll get(int i,int j,int l,int r,int node){
if(j < l || i > r){
return 0;
}
if(l <= i && r >= j){
return drvo[node];
}
int mid = i+(j-i)/2;
return get(i,mid,l,r,2*node)+get(mid+1,j,l,r,2*node+1);
}
set <int> s[2*N];
ll count_swaps(vector <int> v){
n = v.size();
for(int i = 1; i <= n; i++){
a[i] = v[i-1];
}
for(int i = 1; i <= n; i++){
s[a[i]+n].insert(i);
}
build(1,n,1);
ll sol = 0;
for(int i = 1; i <= n; i++){
if(gotov[i]){
continue;
}
ll poz = *s[-a[i]+n].begin();
s[a[i]+n].erase(i);
s[-a[i]+n].erase(poz);
sol += get(1,n,i,poz,1)-2;
if(a[i] > 0){
sol++;
}
//cout << i << " " << poz << " " << sol << endl;
update(1,n,i,1);
update(1,n,poz,1);
gotov[i] = gotov[poz] = 1;
}
return sol;
}
/*int main(){
vector <int> v = {2, 1, -1, -2};
cout << count_swaps(v) << endl;
}*/
# | 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... |