| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 724960 | dooompy | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
map<int, vector<int>> m;
vector<pair<int, int>> pairs;
int bit[300005];
void add(int p, int v) {
p++;
for (int i = p; i < 300005; i+= i & -i) bit[i] += v;
}
ll res(int p) {
p++;
ll sum = 0;
for (; p; p -= p & -p) {
sum += bit[p];
}
return sum;
}
long long count_swaps(vector<int> s) {
for (int i = 0; i < s.size(); i++) {
m[s[i]].push_back(i);
}
ll ans = 0;
for (int i = 1; i <= s.size(); i++) {
for (int j = 0; j < m[i].size(); j++) {
int x = m[i][j], y = m[-i][j];
if (x < y) ans++;
else swap(x, y);
pairs.push_back({x, y});
}
}
sort(pairs.begin(), pairs.end());
for (int i = 0; i < s.size(); i++) add(i, 1);
for (auto [a, b] : pairs) {
add(a, -1);
add(b, -1);
ans += res(b);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
}