| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 679054 | kusssso | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int n;
int bit[N];
ll ans;
vector<int> pos[N][2];
void Update (int p, int v) {
for (int i = p; i < N; i += i & -i) bit[i] += v;
}
int Get (int p) {
int ret = 0;
for (int i = p; i >= 1; i -= i & -i) ret += bit[i];
return ret;
}
int Get (int l, int r) {
return Get(r) - Get(l - 1);
}
ll count_swaps (vector<int> S) {
n = S.size();
for (int i = 1; i <= n; i++) {
Update(i, 1);
pos[abs(S[i - 1])][S[i - 1] < 0].push_back(i);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 2; j++) {
reverse(pos[i][j].begin(), pos[i][j].end());
}
}
for (int i = 1; i <= n; i++) {
if (!S[i - 1])
continue;
int &x = S[i - 1];
// cerr << x << '\n';
int t = (x < 0);
int j = pos[abs(x)][t ^ 1].back();
pos[abs(x)][t ^ 1].pop_back();
pos[abs(x)][t].pop_back();
x = 0;
S[j - 1] = 0;
Update(j, -1);
ans += (t ? Get(i + 1, j) : Get(i, j));
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<int> S = {2, 1, -1, -2};
cout << count_swaps(S);
return 0;
}