이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define pb push_back
#define ff(j, a, b) for(int j=a;j<b;j++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
const int MAXN = 200005;
struct bit{
int tree[MAXN];
void add(int x, int v){
for(int i=x; i<MAXN; i+=i&-i) tree[i] += v;
}
int query(int x){
int ret = 0;
for(int i=x; i; i-=i&-i) ret += tree[i];
return ret;
}
}bit;
ll count_swaps(vector<int> s) {
int n = s.size() / 2;
ll ret = 0;
vector<pint> v;
vector<pint> ord[MAXN];
ff(i, 0, 2*n)
{
ord[abs(s[i])].pb(pint(s[i], i));
}
ff(i, 1, n+1)
{
sort(ord[i].begin(), ord[i].end());
for(int j=0; j<sz(ord[i])/2; j++){
int l = ord[i][j].second;
int r = ord[i][j + ord[i].size()/2].second;
if(l > r){
swap(l, r);
ret++;
}
v.pb(pint(l + 1, r + 1));
}
}
ff(i, 1, 2*n+1) bit.add(i, 1);
sort(v.begin(), v.end());
for(auto &i : v){
ret += bit.query(i.second - 1) - bit.query(i.first);
bit.add(i.first, -1);
bit.add(i.second, -1);
}
return ret;
}
# | 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... |