이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
using namespace std;
template<typename T>
struct BIT
{
vector<T>it;
BIT(int n,T s)
{
it = vector<T>(n,s);
}
void comb(T &x,T &y)
{
x += y;
}
void update(int x,T u)
{
while(x)
{
comb(it[x],u);
x -= x&(-x);
}
}
T query(int x)
{
T ans = it[0];
while(x < (int)it.size())
{
comb(ans,it[x]);
x += x&(-x);
}
return ans;
}
};
long long count_swaps(vector<int> s)
{
int n = s.size()/2, i;
BIT<int>T(n * 2 + 1, 0);
vector<vector<int>>memo(n * 2 + 1);
for(i = n * 2 - 1; i >= 0; i--)
memo[s[i] + n].push_back(i);
long long ans = 0;
for(i = 0; i < n * 2; i++)
{
int x = s[i] + n;
int y = -s[i] + n;
if(memo[x].size()==0 || memo[x].back() != i)continue;
int z = memo[y].back();
ans += z - i - T.query(i+1) + T.query(z + 1);
if(s[i] < 0) ans --;
T.update(z + 1,1);
memo[x].pop_back();
memo[y].pop_back();
}
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... |