Submission #298283

#TimeUsernameProblemLanguageResultExecution timeMemory
298283emil_physmathArranging Shoes (IOI19_shoes)C++17
45 / 100
125 ms27268 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; using llong = long long; #define BUGO(x) cerr << #x << " = " << x << '\n'; const int maxN = 200'005; int t[maxN * 4]; vector<int> chng; void Add(int v, int vl, int vr, int i, int val) { chng.push_back(v); if (vl == vr) { t[v] = val; return; } int vm = vl + (vr - vl) / 2; if (i <= vm) Add(v * 2, vl, vm, i, val); else Add(v * 2 + 1, vm + 1, vr, i, val); t[v] = t[v * 2] + t[v * 2 + 1]; } int Count(int v, int vl, int vr, int l, int r) { if (l > vr || vl > r) return 0; if (l <= vl && vr <= r) return t[v]; int vm = vl + (vr - vl) / 2; return Count(v * 2, vl, vm, l, r) + Count(v * 2 + 1, vm + 1, vr, l, r); } vector<int> pos_[maxN]; vector<int>* pos = pos_ + maxN; long long count_swaps(vector<int> a) { int n = a.size(); if (n <= 16) { for (int i = 0; i < n; ++i) pos[a[i]].push_back(i); for (int i = -n; i <= n; ++i) reverse(pos[i].begin(), pos[i].end()); llong ans = 0; for (int i = 0; i < n; i += 2) { if (abs(a[i]) == abs(a[i + 1]) && a[i] < 0 && a[i + 1] > 0) { pos[a[i]].pop_back(); pos[a[i + 1]].pop_back(); continue; } int j = pos[-a[i]].back(); pos[-a[i]].pop_back(); while (j > i + 1) { ++ans; swap(a[j - 1], a[j]); --j; } if (a[i] > 0) { swap(a[i], a[i + 1]); ++ans; } pos[a[i]].pop_back(); } return ans; } llong ans = 0; int l = 0, r = 0; vector<int> pos(n); for (int i = 0; i < n; ++i) if (a[i] < 0) pos[i] = l++ * 2; else pos[i] = r++ * 2 + 1; for (int i = 0; i < n; ++i) { ans += Count(1, 0, n - 1, pos[i], n - 1); Add(1, 0, n - 1, pos[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...