Submission #1230455

#TimeUsernameProblemLanguageResultExecution timeMemory
1230455neisennArranging Shoes (IOI19_shoes)C++20
0 / 100
1096 ms320 KiB
#include "shoes.h" #include <iostream> #include <vector> #include <map> #include <queue> using namespace std; struct BIT { vector<int> f; int n; void init(int _n){ f.resize(2*_n+2, 0); n = _n; } void add(int x, int v){ for (int i = x; i <= n; i += i & -i){ f[i] += v; } } int query(int l){ int ret = 0; for (int i = l; i > 0; i -= i & -i){ ret += f[i]; } return ret; } int query(int l, int r){ return query(r)-query(l-1); } }; long long count_swaps(std::vector<int> s){ int n = s.size()/2; BIT bit; bit.init(n); map<int, priority_queue<int, vector<int>, greater<int>>> l, r; for (int i = 0; i < 2*n; i++){ if (s[i] < 0){ l[abs(s[i])].push(i); } else { r[s[i]].push(i); } } vector<bool> vis(2*n+1, 0); long long ans = 0; for (int i = 0; i < 2*n; i++){ if (!vis[i]){ int id; if (s[i] < 0) id = r[abs(s[i])].top(); else id = l[s[i]].top(); l[abs(s[i])].pop(); r[abs(s[i])].pop(); ans += abs(id-i)-1; ans -= bit.query(i+1, id); bit.add(id, 1); vis[i] = 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...