제출 #287208

#제출 시각아이디문제언어결과실행 시간메모리
287208Haunted_CppArranging Shoes (IOI19_shoes)C++17
50 / 100
73 ms28664 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5 + 5; vector<vector<int>> L(MAX_N), R(MAX_N); bitset<MAX_N> solved; class FenwickTree { private: vector<int> bit; const int L; public: FenwickTree(int n) : L(n + 5) { bit.clear(); bit.resize(L); } void update(int idx, int delta) { for (; idx < L; idx += idx & (- idx)) { bit[idx] += delta; } } void range_update(int lo, int hi, int delta) { ++lo; ++hi; update(lo, +delta); update(hi + 1, -delta); } int query(int idx) { ++idx; int res = 0; for (; idx > 0; idx -= idx & (- idx)) { res += bit[idx]; } return res; } }; long long count_swaps(vector<int> s) { const int n = s.size(); for (int i = 0; i < n; i++) { const int cur = abs(s[i]); if (s[i] < 0) { L[cur].emplace_back(i); } else { R[cur].emplace_back(i); } } for (int i = 0; i < MAX_N; i++) { reverse(L[i].begin(), L[i].end()); reverse(R[i].begin(), R[i].end()); } FenwickTree fen(n); auto get_idx = [&](int idx) { return idx + fen.query(idx); }; long long res = 0; for (int i = 0; i < n; i++) { if (solved[i]) continue; const int cur = abs(s[i]); int lo = i; int hi; if (s[i] > 0) { R[cur].pop_back(); hi = L[cur].back(); L[cur].pop_back(); } else { L[cur].pop_back(); hi = R[cur].back(); R[cur].pop_back(); } solved[lo] = solved[hi] = 1; res += (s[i] > 0) + get_idx(hi) - get_idx(lo) - 1; fen.range_update(lo, hi, + 1); } return res; }
#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...