제출 #283539

#제출 시각아이디문제언어결과실행 시간메모리
283539ipaljakArranging Shoes (IOI19_shoes)C++14
50 / 100
311 ms53112 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define TRACE(x) cerr << #x << " " << x << endl #define _ << " " << typedef long long llint; const int MAXN = 1e5 + 5; bool bio[MAXN]; int n; int nxt[2 * MAXN], loga[2 * MAXN]; vector<int> s; void init() { memset(nxt, -1, sizeof nxt); map<int, vector<int>> m; for (int i = 0; i < n; ++i) m[s[i]].push_back(i); for (auto &p : m) { assert(p.second.size() == m[-p.first].size()); for (int i = 0; i < (int) p.second.size(); ++i) { nxt[p.second[i]] = m[-p.first][i]; nxt[m[-p.first][i]] = p.second[i]; } } } void add(int i) { for (; i < 2 * MAXN; i += i & -i) loga[i]++; } int sum(int lo, int hi) { int ret = 0; for (; hi > 0; hi -= hi & -hi) ret += loga[hi]; for (--lo; lo > 0; lo -= lo & -lo) ret -= loga[lo]; return ret; } llint count_swaps(vector<int> _s) { s = _s; n = (int) s.size(); init(); llint sol = 0; for (int i = 0; i < n; ++i) { if (bio[i]) continue; assert(nxt[i] > i); int l = i, r = nxt[i]; bio[l] = bio[r] = true; sol += (llint) r - l - 1; sol -= sum(l + 1, r + 1); add(l + 1); add(r + 1); if (s[i] > 0) ++sol; } return sol; }
#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...