제출 #1148049

#제출 시각아이디문제언어결과실행 시간메모리
1148049gulmixArranging Shoes (IOI19_shoes)C++20
100 / 100
143 ms27004 KiB
#include "shoes.h" #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; using ll = long long; #define all(x) x.begin(), x.end() #define oset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> struct BIT{ vector<ll> bit; ll n; BIT(){} BIT(ll n): n(n){ bit.resize(n + 1, 0); } void update(ll u, ll x){ for(u; u <= n; u += (u & -u))bit[u]+=x; } ll get(ll u){ ll ans = 0; for(u; u > 0; u -= (u & -u))ans += bit[u]; return ans; } ll get(ll l, ll r){ return get(r) - get(l-1); } }; vector<ll> d[200007]; vector<ll> l[200007], r[200007]; bool cmp(vector<ll> a, vector<ll> b) { return min(a[0], a[1]) < min(b[0], b[1]); } ll count_swaps(vector<int> s) { for(int i = 0; i < s.size(); i++) { if(s[i] < 0) { l[-s[i]].push_back(i + 1); } else { r[s[i]].push_back(i + 1); } } ll n = s.size() / 2; ll c = 0; for(int i = 1; i <= n; i++) { for(int j = 0; j < l[i].size(); j++) { d[++c].push_back(r[i][j]); d[c].push_back(l[i][j]); } } sort(d + 1, d + c + 1, cmp); BIT bit = BIT(s.size() + 1); ll ans = 0; for(int i = 1; i <= c; i++) { for(int j = 1; j >= 0; j--) { ll pos = i * 2 - j; ll sus = d[i][j] + bit.get(d[i][j] + 1, s.size()); bit.update(d[i][j], 1); ans += abs(sus - pos); } } 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...