Submission #386935

#TimeUsernameProblemLanguageResultExecution timeMemory
386935danielcm585Arranging Shoes (IOI19_shoes)C++14
100 / 100
208 ms139516 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5; const int ADD = 1e5; int n; int pr[N+2], bit[N+2]; queue<int> ls[N+2]; void update(int x, int v) { for (int i = x+1; i <= n; i += i&-i) bit[i] += v; } int query(int x, int y) { int ret = 0; for (int i = y+1; i; i -= i&-i) ret += bit[i]; for (int i = x; i; i -= i&-i) ret -= bit[i]; return ret; } ll count_swaps(vector<int> s) { n = s.size(); for (int i = 0; i < n; i++) { if (!ls[-s[i]+ADD].empty()) { int x = ls[-s[i]+ADD].front(); ls[-s[i]+ADD].pop(); pr[x] = i; } else ls[s[i]+ADD].push(i); update(i,+1); } ll ans = 0; for (int i = 0; i < n; i++) { if (!pr[i]) continue; ans += query(i+1,pr[i]-1) + (s[i] > 0); update(pr[i],-1); } return ans; } /* 3 -2 2 2 -2 -2 2 3 -2 3 4 2 -4 -3 */
#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...