제출 #978018

#제출 시각아이디문제언어결과실행 시간메모리
978018kilkuwuArranging Shoes (IOI19_shoes)C++17
100 / 100
443 ms36268 KiB
#include "shoes.h" #include <bits/stdc++.h> struct SegmentTree { int n; std::vector<int> t; SegmentTree(int _n) : n(_n), t(2 * n) {} void update(int l, int r, int v) { for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) t[l] += v, l++; if (r & 1) --r, t[r] += v; } } int query(int p) { int ans = 0; for (p += n; p > 0; p >>= 1) { ans += t[p]; } return ans; } }; long long count_swaps(std::vector<int> s) { int n = (int) s.size() / 2; SegmentTree tree(2 * n); for (int i = 0; i < 2 * n; i++) { tree.update(i, i + 1, i); } std::map<int, std::vector<int>> mp; std::set<std::pair<int, int>> st; for (int i = 2 * n; i >= 0; i--) { mp[s[i]].push_back(i); st.insert({i, s[i]}); } long long ans = 0; for (int i = 0; i < n; i++) { int f = 2 * i; int v = st.begin()->second; auto pos = mp[-v].back(); mp[-v].pop_back(); mp[v].pop_back(); int real_pos = tree.query(pos); ans += real_pos - (f + (v < 0)); tree.update(0, pos, 1); st.erase(st.begin()); st.erase({pos, s[pos]}); } 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...