Submission #867417

#TimeUsernameProblemLanguageResultExecution timeMemory
867417lolismekArranging Shoes (IOI19_shoes)C++14
50 / 100
27 ms15964 KiB
#include "shoes.h" #include <queue> #define pii pair <int, int> using namespace std; const int NMAX = 1e5; namespace AIB{ int n; int aib[NMAX + 1]; void init(int _n){ n = _n; } int lsb(int x){ return x & -x; } void update(int pos, int val){ pos += 1; for(int i = pos; i <= n; i += lsb(i)){ aib[i] += val; } } int query(int pos){ pos += 1; int ans = 0; for(int i = pos; i >= 1; i -= lsb(i)){ ans += aib[i]; } return ans; } } vector <int> pos[NMAX + 1]; int par[NMAX + 1]; bool viz[NMAX + 1]; long long count_swaps(vector<int> s){ int n = (int)s.size(); for(int i = 0; i < n; i++){ pos[(s[i] < 0 ? -s[i] : s[i])].push_back(i); } for(int col = 1; col <= n; col++){ queue <pii> St; for(int j = 0; j < (int)pos[col].size(); j++){ int i = pos[col][j]; if(!St.empty() && St.front().first == -s[i]){ par[i] = St.front().second; par[St.front().second] = i; St.pop(); }else{ St.push({s[i], i}); } } } AIB::init(n); for(int i = 0; i < n; i++){ AIB::update(i, +1); } long long ans = 0; for(int i = 0; i < n; i++){ if(!viz[i]){ viz[i] = viz[par[i]] = true; AIB::update(i, -1); AIB::update(par[i], -1); ans += AIB::query(par[i]) - AIB::query(i) + (s[i] > s[par[i]]); } } 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...