제출 #479419

#제출 시각아이디문제언어결과실행 시간메모리
479419thiago_bastosArranging Shoes (IOI19_shoes)C++17
100 / 100
120 ms21876 KiB
#include "shoes.h" using namespace std; template<class T> struct BIT { vector<T> bit; BIT(int n) { bit.assign(n + 1, 0); } void upd(int k, T x) { for(++k; k < int(bit.size()); k += k & -k) bit[k] += x; } T query(int k) { T ans {}; for(++k; k > 0; k -= k & -k) ans += bit[k]; return ans; } T query(int l, int r) { if(l > r) return (T)0; return query(r) - query(l - 1); } }; long long count_swaps(vector<int> s) { int n = s.size(), id = 0; vector<vector<int>> pos(n + 1), neg(n + 1); vector<int> loPos(n + 1, 0), loNeg(n + 1, 0); vector<bool> marked(n, false); for(int i = 0; i < n; ++i) { if(s[i] < 0) neg[-s[i]].push_back(i); else pos[s[i]].push_back(i); } for(int i = 0; i < n; ++i) { if(marked[i]) continue; if(s[i] < 0) { int k = pos[-s[i]][loPos[-s[i]]++]; ++loNeg[-s[i]]; s[k] = id + 1; s[i] = id; marked[k] = true; } else { int k = neg[s[i]][loNeg[s[i]]++]; ++loPos[s[i]]; s[k] = id; s[i] = id + 1; marked[k] = true; } id += 2; } BIT<long long> bit(n); auto ans = 0LL; for(int v : s) { ans += bit.query(v + 1, n - 1); bit.upd(v, 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...