| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1286393 | harryleee | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
inline long long count_swaps(const vector<int>& a){
// n = số cặp (mảng a có 2n phần tử)
int n = (int)a.size() / 2;
// tạo queues sau khi đã có n
vector<queue<int>> q(2 * n + 1);
vector<int> last_ind(a.size());
for (int i = 0; i < (int)a.size(); ++i){
// kiểm tra queue của "đối dấu" cùng kích cỡ
if (q[-a[i] + n].empty()){
q[a[i] + n].push(i);
last_ind[i] = i;
}
else{
int pre = q[-a[i] + n].front();
q[-a[i] + n].pop();
last_ind[i] = pre;
}
}
struct SEGMENT_TREE{
vector<vector<int>> st;
inline SEGMENT_TREE(int m, const vector<int>& vec){
st.resize(4 * m);
build(1, 0, m - 1, vec);
}
inline void build(int ind, int l, int r, const vector<int>& vec){
if (l == r){
st[ind].push_back(vec[l]);
return;
}
int mid = (l + r) >> 1;
build(ind << 1, l, mid, vec);
build(ind << 1 | 1, mid + 1, r, vec);
const vector<int>& L = st[ind << 1];
const vector<int>& R = st[ind << 1 | 1];
vector<int> tmp;
tmp.reserve(L.size() + R.size());
size_t i = 0, j = 0;
while (i < L.size() && j < R.size()){
if (L[i] <= R[j]) tmp.push_back(L[i++]);
else tmp.push_back(R[j++]);
}
while (i < L.size()) tmp.push_back(L[i++]);
while (j < R.size()) tmp.push_back(R[j++]);
st[ind].swap(tmp);
}
inline long long get(int ind, int l, int r, int lb, int rb, int val){
if (lb > rb) return 0;
if (lb <= l && r <= rb){
int it = upper_bound(st[ind].begin(), st[ind].end(), val) - st[ind].begin();
return (long long)st[ind].size() - it;
}
int mid = (l + r) >> 1;
long long ans = 0;
if (lb <= mid) ans += get(ind << 1, l, mid, lb, rb, val);
if (rb > mid) ans += get(ind << 1 | 1, mid + 1, r, lb, rb, val);
return ans;
}
};
// xây cây trên last_ind (kích thước m = a.size())
SEGMENT_TREE seg((int)a.size(), last_ind);
long long res = 0;
for (int i = 0; i < (int)a.size(); ++i) if (last_ind[i] != i){
res += seg.get(1, 0, (int)a.size() - 1, last_ind[i] + 1, i - 1, last_ind[i]);
if (a[last_ind[i]] > 0) res++;
}
return res;
}