제출 #143658

#제출 시각아이디문제언어결과실행 시간메모리
143658mosesmayerArranging Shoes (IOI19_shoes)C++17
100 / 100
262 ms122920 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int mxsz = 1e5 + 5; const int MX = 2e5; int n; deque<int> dq[mxsz]; int match[MX + 5]; bool done[MX + 5]; long long ans = 0, invcnt = 0; struct FenwickTree{ int ft[MX + 5]; FenwickTree(){} void upd(int p, int v){ for (; p <= MX; p += p & -p) ft[p] += v; } int get(int p){ int ret = 0; for (; p > 0; p -= p & -p) ret += ft[p]; return ret; } } ft; long long count_swaps(std::vector<int> s) { n = s.size(); n >>= 1; for (int i = 0; i < 2 * n; i++){ int u = abs(s[i]); if (s[i] < 0){ if (!dq[u].empty() && s[dq[u].back()] > 0){ int v = dq[u].back(); dq[u].pop_back(); match[i] = v; match[v] = i; invcnt++; } else dq[u].push_back(i); } else { if (!dq[u].empty() && s[dq[u].front()] < 0){ int v = dq[u].front(); dq[u].pop_front(); match[i] = v; match[v] = i; } else dq[u].push_front(i); } } for (int i = 0; i < 2 * n; i++){ if (done[i]) continue; int u = match[i]; ans += u - i - 1 - (ft.get(u+1) - ft.get(i)); ft.upd(i + 1, 1); ft.upd(u+1, 1); done[u] = done[i] = 1; } return ans + invcnt; }
#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...