이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
int seg[400001];
void build(int p,int l,int r){
if(l==r){
seg[p] = 0;
return ;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[p] = seg[p*2]+seg[p*2+1];
}
void update(int p,int l,int r,int idx,int val){
if(l==r){
seg[p]+=val;
return ;
}
int md = (l+r)/2;
if(idx<=md)update(p*2,l,md,idx,val);
else update(p*2+1,md+1,r,idx,val);
seg[p] = seg[p*2]+seg[p*2+1];
}
int query(int p,int l,int r,int lq,int rq){
if(l>=lq&&r<=rq)return seg[p];
if(r<lq||l>rq)return 0;
int md = (l+r)/2;
return query(p*2,l,md,lq,rq)+query(p*2+1,md+1,r,lq,rq);
}
long long count_swaps(vector<int> s){
int n = s.size();
map<int,stack<int>> v;
long long ans = 0;
for(int i = 0;i<n;i++){
if(v[-s[i]].size()==0){
v[s[i]].push(i);update(1,0,n,i,1);}
else{
ans+=(i-query(1,0,n,0,v[-s[i]].top()));
update(1,0,n,v[-s[i]].top(),1);
v[-s[i]].pop();
if(s[i]<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... |