제출 #686706

#제출 시각아이디문제언어결과실행 시간메모리
686706BliznetcArranging Shoes (IOI19_shoes)C++17
100 / 100
625 ms150748 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define sz size() #define all(x) x.begin(), x.end() #define F first #define S second typedef pair < int, int > pii; typedef vector < int > vi; typedef vector < vi > vvi; int t[800400]; void upd (int v, int l, int r, int pos) { if (l > pos || r < pos){ return; } if (l == r) { t[v] = 1; return; } int mid = (l + r) / 2; upd(2 * v, l, mid, pos); upd(2 * v + 1, mid + 1, r, pos); t[v] = t[2 * v] + t[2 * v + 1]; } int get_sum (int v, int l, int r, int tl, int tr) { if (l > tr || r < tl) { return 0; } if (l >= tl && r <= tr) { return t[v]; } int mid = (l + r) / 2; return get_sum(2 * v, l, mid, tl, tr) + get_sum(2 * v + 1, mid + 1, r, tl, tr); } long long count_swaps(vector<int> b) { int n = b.sz; int a[n + 7]; int used[n + 7]; for (int i = 0; i < n; i++) { a[i + 1] = b[i]; used[i + 1] = 0; } map <int, deque<int> > m; for (int i = 1; i <= n; i++) { m[a[i]].pb(i); } long long cnt = 0, ans = 0; for (int i = 1; i <= n; i++) { if (used[i]) { continue; } if (a[i] > 0) { int pos = m[-a[i]].front(); cnt = get_sum (1, 1, n, i, pos); ans += pos - i - cnt; used[pos] = 1; upd(1, 1, n, pos); m[a[i]].pop_front(); m[-a[i]].pop_front(); } else { int pos = m[-a[i]].front(); cnt = get_sum (1, 1, n, i, pos); ans += pos - i - 1 - cnt; used[pos] = 1; upd(1, 1, n, pos); m[a[i]].pop_front(); m[-a[i]].pop_front(); } // cout << i << " " << ans << "\n"; } return ans; } /* signed main() { vi a; a.pb(-2); a.pb(2); a.pb(2); a.pb(-2); a.pb(-2); a.pb(2); cout << count_swaps(a); } */
#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...