이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int N = 2e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
#include "shoes.h"
vector <int> pos[2 * N];
int bit[N];
int n;
void update(int pos, int val) {
pos++;
for (; pos <= n; pos += pos & -pos)
bit[pos] += val;
}
int getval(int pos) {
int res = 0;
pos++;
for (; pos; pos -= pos & -pos)
res += bit[pos];
return res;
}
long long count_swaps(std::vector<int> s) {
n = s.size();
vector <pair <int, int>> p;
for (int i = n - 1; i >= 0; i--)
pos[s[i] + n].push_back(i);
for (int i = 0; i < n; i++) {
if (!pos[s[i] + n].size() || pos[s[i] + n].back() != i)
continue;
p.push_back(mp(pos[-s[i] + n].back(), i));
pos[-s[i] + n].pop_back();
pos[s[i] + n].pop_back();
}
sort(ALL(p));
for (int i = 0; i < n; i++)
update(i, 1);
long long ans = 0;
for (pair <int, int> pir : p) {
// cerr << pir.fi << " " << pir.se << "\n";
ans += getval(pir.fi) + getval(pir.se) - 3;
update(pir.fi, -1);
update(pir.se, -1);
ans += (s[pir.fi] < 0);
}
return ans;
}
//#include "grader.cpp"
# | 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... |