제출 #230181

#제출 시각아이디문제언어결과실행 시간메모리
230181chubyxdxdArranging Shoes (IOI19_shoes)C++17
10 / 100
1095 ms384 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; ll tree[200100]; ll tam; void update(ll pos,ll val){ while(pos<=tam){ tree[pos]+=val; pos+=(pos&-pos); } } ll query(ll pos){ ll curr=0; while(pos>0){ curr+=tree[pos]; pos-=(pos&-pos); } return curr; } unordered_map<ll,set<ll> > mp; long long count_swaps(std::vector<int> s) { tam=s.size(); bool vis[tam]; memset(vis,0,sizeof vis); for(int i=0;i<tam;i++){ mp[s[i]].insert(i); } set<ll>::iterator it,it1; ll ans=0; for(int i=0;i<tam-1;i++){ if(vis[i])continue; vis[i]=1; mp[s[i]].erase(i); if(s[i]>0){ it=mp[(s[i]*-1)].begin(); mp[s[i]*-1].erase(it); ll aux=*it; ll curr=i+query(i+1ll); ll curr1=aux+query(aux+1ll); ll currans=curr1-curr; vis[aux]=1; update(i+1,1); update(aux+1,-1); ans+=currans; } else{ it=mp[s[i]*-1].begin(); mp[s[i]*-1].erase(it); ll aux=*it; ll curr=i+query(i+1ll); ll curr1=aux+query(aux+1ll); ll currans=curr1-(curr+1); ans+=currans; //cout<<currans<<endl; if(currans!=0){ update(i+2,1); update(aux,-1); } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...