Submission #1114858

#TimeUsernameProblemLanguageResultExecution timeMemory
1114858anmattroiArranging Shoes (IOI19_shoes)C++14
45 / 100
70 ms10588 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; long long count_swaps(std::vector<int> s) { int n = int(s.size()) / 2; s.insert(s.begin(), 0); vector<int> bit(n+n+1, 0), a(n+n+1, 0); vector<int> b(1); for (int i = 1; i <= n+n; i++) { if (s[i] > 0) b.emplace_back(s[i]); } sort(b.begin()+1, b.end()); for (int i = 1; i <= n+n; i++) { if (s[i] > 0) { s[i] = lower_bound(b.begin()+1, b.end(), s[i]) - b.begin(); } else s[i] = -(lower_bound(b.begin()+1, b.end(), -s[i]) - b.begin()); } function<void(int, int)> upd = [&](int u, int d) { for (int i = u; i > 0; i -= i & -i) bit[i] += d; }; function<int(int)> get = [&](int u) { int kq = 0; for (int i = u; i <= n+n; i += i & -i) kq += bit[i]; return kq; }; vector<vector<int> > nho(n+1, vector<int>(0)); int cnt = 0; for (int i = 1; i <= n+n; i++) { if (s[i]<0) { ++cnt; a[i] = cnt*2-1; nho[-s[i]].emplace_back(a[i]+1); } } for (int i = 1; i <= n; i++) reverse(nho[i].begin(), nho[i].end()); for (int i = 1; i <= n+n; i++) { if (s[i]<0) continue; a[i] = nho[s[i]].back(); nho[s[i]].pop_back(); } long long kq = 0; for (int i = 1; i <= n+n; i++) { kq += get(a[i]); upd(a[i], 1); } return kq; }
#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...