This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+5;
struct fenwick {
int t[MX];
void upd(int v, int x) {
v++;
for(int i=v;i<MX;i+=i&-i) t[i]+=x;
}
int que(int v) {
v++;
int res=0;
for(int i=v;i>0;i-=i&-i) res+=t[i];
return res;
}
} ft;
map<int, vector<int>> pos;
long long count_swaps(vector<int> S) {
int N=S.size()/2;
ll ans=0;
for(int i=0;i<2*N;i++) ft.upd(i,1);
set<int> st;
for(int i=2*N-1;i>=0;i--) {
pos[S[i]].push_back(i);
st.insert(i);
}
for(int i=1;i<2*N;i+=2) {
int b=*st.begin();
ft.upd(b,-1);
st.erase(st.begin());
pos[S[b]].pop_back();
int j=pos[-S[b]].back();
pos[-S[b]].pop_back();
ft.upd(j,-1);
st.erase(j);
ans+=ft.que(j);
if(S[b]>0) {
ans++;
}
}
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... |