이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200005
int p[N], arr[N], tmp[N];
bool visit[N];
vector<int> idx[N];
int sgn(int n)
{
return (n < 0) ? -1 : 1;
}
long long inv(int l, int r)
{
if(l == r) return 0;
int mid = (l+r)>>1;
long long ret = inv(l, mid) + inv(mid+1, r);
int i = l, j = mid+1, k = l;
while(i <= mid && j <= r)
{
if(arr[i] < arr[j]) tmp[k++] = arr[i++];
else
{
ret += mid-i+1;
tmp[k++] = arr[j++];
}
}
while(i <= mid) tmp[k++] = arr[i++];
while(j <= r) tmp[k++] = arr[j++];
for(int i=l ; i<=r ; i++) arr[i] = tmp[i];
return ret;
}
long long count_swaps(vector<int> s)
{
int n = s.size(), now = 1;
for(int i=0 ; i<n ; i++) idx[s[i]+100000].push_back(i);
for(int i=0 ; i<n ; i++)
{
if(visit[i]) continue ;
arr[i] = now * sgn(s[i]);
arr[idx[100000-s[i]][p[100000-s[i]]]] = -arr[i];
visit[i] = true;
visit[idx[100000-s[i]][p[100000-s[i]]]] = true;
p[100000+s[i]]++;
p[100000-s[i]]++;
now++;
}
for(int i=0 ; i<n ; i++)
{
int d = 2 * abs(arr[i]);
if(arr[i] > 0) d++;
arr[i] = d;
}
return inv(0, n-1);
}
# | 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... |