제출 #772697

#제출 시각아이디문제언어결과실행 시간메모리
772697Abrar_Al_SamitArranging Shoes (IOI19_shoes)C++17
100 / 100
265 ms22708 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; const int nax = 2e5 + 3; struct bit { int a[nax] = {0}; void add(int i) { while(i<nax) { ++a[i]; i += i&-i; } } int query(int i) { int ret = 0; while(i>0) { ret += a[i]; i -= i&-i; } return ret; } int query(int l, int r) { if(l==0) return query(r); return query(r) - query(l-1); } } b; long long count_swaps(vector<int> s) { int n = s.size(); set<pair<int,int>>by_index, by_color; for(int i=0; i<n; ++i) { by_index.insert(make_pair(i, s[i])); by_color.insert(make_pair(s[i], i)); } long long ans = 0; int cur_index = 0; while(!by_index.empty()) { auto x = *by_index.begin(); by_index.erase(x); by_color.erase(make_pair(x.second, x.first)); auto y = *by_color.lower_bound(make_pair(-x.second, -1)); by_color.erase(y); by_index.erase(make_pair(y.second, y.first)); if(x.second>0) ++ans; //find real index of y.second int inc = b.query(y.second, n); int real_index = y.second + inc; ans += real_index - cur_index - 1; b.add(y.second); cur_index += 2; } 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...