| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 489914 | kevin | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";
struct BIT {
vector<int> f;
int n;
void init(int N) { f = vector<int>(N+1, 0); n = N;}
int lsb(int x) { return x & -x; }
void update(int p, int v){
while(p <= n){ f[p] += v; p += lsb(p); }
}
int query(int p) {
int sum = 0;
while (p > 0) { sum += f[p]; p -= lsb(p); }
return sum;
}
};
ll count_swaps(vector<int> ar){
int n = ((int)ar.size()) / 2;
queue<int> pos[n+1][2];
vector<int> ord;
for(int i=0; i<2*n; i++){
if(ar[i] < 0) {
pos[-ar[i]][0].push(i+1);
ord.push_back(-ar[i]);
}
else pos[ar[i]][1].push(i+1);
}
BIT fen; fen.init(n+5);
ll ans = 0;
for(int k=1; k<=n; k++){
int x = ord[k-1];
int i = pos[x][0].front(); pos[x][0].pop();
int j = pos[x][1].front(); pos[x][1].pop();
// cout<<x<<" "<<i<<" "<<j<<"\n";
ans += i+fen.query(i) - (2*k-1);
fen.update(1, 1); fen.update(i, -1);
// cout<<ans<<" ";
ans += j+fen.query(j) - 2*k;
// cout<<ans<<" ";
fen.update(1, 1); fen.update(j, -1);
// nl;
}
return ans;
return 0;
}
int main()
{
// ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
int n; cin>>n;
vector<int> ar(2*n);
for(int i=0; i<2*n; i++) cin>>ar[i];
cout<<count_swaps(ar);
}