이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
// -------------------- Typedefs -------------------- //
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
// -------------------- Defines -------------------- //
#define pr pair
#define mpr make_pair
#define ff first
#define ss second
#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue
#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()
#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
// -------------------- Constants -------------------- //
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);
// -------------------- Solution -------------------- //
const int N = 100005;
int f[N * 2];
deque<int> c[N * 2];
bool used[N * 2];
int n;
void upd(int ind)
{
for (int i = ind; i < n * 2; i |= (i + 1)) f[i]++;
return;
}
int qry(int ind)
{
int ans = 0;
for (int i = ind; i >= 0; i = (i & (i + 1)) - 1) ans += f[i];
return ans;
}
int qry(int l, int r)
{
int ans = qry(r);
if (l) ans -= qry(l - 1);
return ans;
}
ll count_swaps(vector<int> a)
{
int i, j;
n = sz(a) / 2;
for (i = 0; i < n * 2; i++) {
if (a[i] > 0) c[a[i]].pb(i);
else c[n - a[i]].pb(i);
}
/*for (i = 1;i <= n * 2;i++) {
for (auto j : c[i]) cout << j << ' ';
cout << "\n";
}*/
ll ans = 0;
for (i = 0; i < n * 2; i++) {
if (used[i]) continue;
if (a[i] < 0) {
j = c[-a[i]].ft();
c[-a[i]].popf();
c[n - a[i]].popf();
used[j] = true;
upd(j);
ans += j - i - 1 - qry(i + 1, j - 1);
}
else {
j = c[n + a[i]].ft();
c[n + a[i]].popf();
c[a[i]].popf();
used[j] = true;
upd(j);
ans += j - i - 1 - qry(i + 1, j - 1) + 1;
}
//cout << ans << "\n";
}
return ans;
}
/*
# # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # #
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |