제출 #1066192

#제출 시각아이디문제언어결과실행 시간메모리
1066192TsovakArranging Shoes (IOI19_shoes)C++17
100 / 100
131 ms139720 KiB
#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <bits/stdc++.h> #include "shoes.h" using namespace std; // -------------------- Typedefs -------------------- // typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; // -------------------- Defines -------------------- // #define pr pair #define mpr make_pair #define ff first #define ss second #define mset multiset #define mmap multimap #define uset unordered_set #define umap unordered_map #define umset unordered_multiset #define ummap unordered_multimap #define pqueue priority_queue #define sz(x) (int((x).size())) #define len(x) (int((x).length())) #define all(x) (x).begin(), (x).end() #define clr(x) (x).clear() #define ft front #define bk back #define pf push_front #define pb push_back #define popf pop_front #define popb pop_back #define lb lower_bound #define ub upper_bound #define bs binary_search // -------------------- Constants -------------------- // const int MAX = int(1e9 + 5); const ll MAXL = ll(1e18 + 5); const ll MOD = ll(1e9 + 7); const ll MOD2 = ll(998244353); // -------------------- Solution -------------------- // const int N = 100005; int f[N * 2]; deque<int> c[N * 2]; bool used[N * 2]; int n; void upd(int ind) { for (int i = ind; i < n * 2; i |= (i + 1)) f[i]++; return; } int qry(int ind) { int ans = 0; for (int i = ind; i >= 0; i = (i & (i + 1)) - 1) ans += f[i]; return ans; } int qry(int l, int r) { int ans = qry(r); if (l) ans -= qry(l - 1); return ans; } ll count_swaps(vector<int> a) { int i, j; n = sz(a) / 2; for (i = 0; i < n * 2; i++) { if (a[i] > 0) c[a[i]].pb(i); else c[n - a[i]].pb(i); } /*for (i = 1;i <= n * 2;i++) { for (auto j : c[i]) cout << j << ' '; cout << "\n"; }*/ ll ans = 0; for (i = 0; i < n * 2; i++) { if (used[i]) continue; if (a[i] < 0) { j = c[-a[i]].ft(); c[-a[i]].popf(); c[n - a[i]].popf(); used[j] = true; upd(j); ans += j - i - 1 - qry(i + 1, j - 1); } else { j = c[n + a[i]].ft(); c[n + a[i]].popf(); c[a[i]].popf(); used[j] = true; upd(j); ans += j - i - 1 - qry(i + 1, j - 1) + 1; } //cout << ans << "\n"; } 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...