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