이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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... |