Submission #1266642

#TimeUsernameProblemLanguageResultExecution timeMemory
1266642canhnam357Ekoeko (COCI21_ekoeko)C++20
110 / 110
8 ms2456 KiB
#include <bits/stdc++.h> using namespace std; struct fenwick { int n; vector<int> bit; fenwick() {} fenwick(int n) { this->n = n + 5; bit.resize(n + 5); } void add(int pos, int val) { while (pos < n) { bit[pos] += val; pos += pos & -pos; } } int get(int pos) { int ans = 0; while (pos) { ans += bit[pos]; pos -= pos & -pos; } return ans; } int get(int l, int r) { return get(r) - get(l - 1); } int find(int k) { int sum = 0, pos = 0; for (int i = __lg(n); i >= 0; i--) { if (pos + (1 << i) < n && sum + bit[pos + (1 << i)] < k) { sum += bit[pos + (1 << i)]; pos += (1 << i); } } return pos + 1; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; string s; cin >> s; string l = "", r = ""; int cnt[26]{}; for (char c : s) { cnt[c - 'a']++; } for (int i = 0; i < 26; i++) { cnt[i] >>= 1; } long long ans = 0; for (char c : s) { if (cnt[c - 'a']) { cnt[c - 'a']--; l += c; ans += r.size(); } else { r += c; } } deque<int> pl[26]; for (int i = 0; i < n; i++) { pl[l[i] - 'a'].push_back(i); } vector<int> p(n); for (int i = 0; i < n; i++) { p[i] = pl[r[i] - 'a'][0]; pl[r[i] - 'a'].pop_front(); } fenwick tree(n); for (int i : p) { i++; ans += tree.get(i + 1, n); tree.add(i, 1); } cout << ans; return 0; }
#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...