| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1356022 | vjudge1 | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MX = 100100;
struct A{
int l,r,mn;
bool operator<(const A&o)const{
return mn<o.mn;
}
};
vector<int>l[MX],r[MX];
vector<A>ord;
int fw[MX],n;
int query(int i){
int ret = 0;
for(;i;i-=(i&-i))ret+=fw[i];
return ret;
}
void upd(int i){
for(;i<=n;i+=(i&-i))fw[i]--;
}
long long count_swaps(std::vector<int> s) {
int N = s.size()/2;
n = s.size();
for(int i=0;i<s.size();i++){
if(s[i]<0)l[-s[i]].push_back(i);
else r[s[i]].push_back(i);
}
for(int i=1;i<=N;i++){
for(int j=0;j<l[i].size();j++){
ord.push_back({l[i][j],r[i][j],min(l[i][j],r[i][j])});
}
}
vector<int>ans(s.size());
sort(ord.begin(),ord.end());
for(int i=0;i<ord.size();i++){
ans[ord[i].l] = i*2;
ans[ord[i].r] = i*2+1;
}
int ret = 0;
for(int i=0;i<s.size();i++){
ret+=i+query(ans[i]+1);
upd(ans[i]+1);
}
return ret;
}
int main() {
int n;
assert(1 == scanf("%d", &n));
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++)
assert(1 == scanf("%d", &S[i]));
fclose(stdin);
long long result = count_swaps(S);
printf("%lld\n", result);
fclose(stdout);
return 0;
}