제출 #378484

#제출 시각아이디문제언어결과실행 시간메모리
378484autumn_eelArranging Shoes (IOI19_shoes)C++14
0 / 100
1 ms364 KiB
#include "shoes.h" #include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<int(n);i++) using namespace std; typedef long long ll; struct BIT{ vector<int>bit; BIT(int n){ bit=vector<int>(n+10); } void add(int k,int x){ k++; while(k<(int)bit.size()){ bit[k]+=x; k+=k&-k; } } int sum(int k){ k++; int res=0; while(k){ res+=bit[k]; k-=k&-k; } return res; } }; long long count_swaps(std::vector<int> s) { BIT bit(s.size()); map<int,set<int>>mp; set<int>se; rep(i,s.size()){ se.insert(i); mp[s[i]].insert(i); bit.add(i,1); } ll ans=0; if(!se.empty()){ int x=*se.begin();se.erase(se.begin()); mp[s[x]].erase(mp[s[x]].begin()); int y=*mp[-s[x]].begin();mp[-s[x]].erase(mp[-s[x]].begin()); se.erase(y); int cnt=bit.sum(y-1); if(s[x]>0)cnt++; bit.add(x,-1); bit.add(y,-1); ans+=cnt; } 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...