제출 #201418

#제출 시각아이디문제언어결과실행 시간메모리
201418khulegubArranging Shoes (IOI19_shoes)C++14
10 / 100
11 ms9720 KiB
#include "shoes.h" #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define xx first #define yy second #define ll(x) (x*2) + 1 #define rr(x) (x*2) + 2 using namespace std; typedef long long i64; int n; int ft[200010]; int query(int x){ int sm = 0; while (x){ sm += ft[x]; x -= x & (-x); } return sm; } int query(int l, int r){ int ll = 0; if (l != 0) ll = query(l - 1); return query(r) - ll; } void update(int x, int v){ while (x < n){ ft[x] += v; x += x & (-x); } } bool taken[200010]; vector<int> maap_l[200010], maap_r[200010]; i64 count_swaps(std::vector<int> s) { i64 ans = 0LL; n = s.size(); for (int i = n - 1; i >= 0; i--){ if (s[i] < 0) maap_l[s[i] * -1].pb(i); else maap_r[s[i]].pb(i); } for (int i = 0; i < n; i++){ if (!taken[i]){ int tmp; if (s[i] < 0){ tmp = maap_r[s[i] * -1].back(); maap_r[s[i] * -1].pop_back(); } else{ tmp = maap_l[s[i]].back(); maap_l[s[i]].pop_back(); } taken[tmp] = 1; if (s[i] < 0){ ans += tmp - i - 1; } else{ ans += tmp - i; } ans -= query(i + 1, tmp + 1); update(tmp + 1, 1); } } 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...