Submission #1215832

#TimeUsernameProblemLanguageResultExecution timeMemory
1215832szz0liArranging Shoes (IOI19_shoes)C++20
25 / 100
217 ms39536 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll maxN = 2e5+5; vector<ll> t; void build(ll v, ll tl, ll tr) { if (tl == tr) { t[v] = 1; } else { ll tm = (tl + tr) / 2; build(v*2, tl, tm); build(v*2+1, tm+1, tr); t[v] = t[v*2] + t[v*2+1]; } } ll sum(ll v, ll tl, ll tr, ll l, ll r) { if (l > r) return 0; if (l == tl && r == tr) { return t[v]; } ll tm = (tl + tr) / 2; return sum(v*2, tl, tm, l, min(r, tm)) + sum(v*2+1, tm+1, tr, max(l, tm+1), r); } void update(ll v, ll tl, ll tr, ll pos, ll new_val) { if (tl == tr) { t[v] = new_val; } else { ll tm = (tl + tr) / 2; if (pos <= tm) update(v*2, tl, tm, pos, new_val); else update(v*2+1, tm+1, tr, pos, new_val); t[v] = t[v*2] + t[v*2+1]; } } ll count_swaps(vector<int>v){ ll n = v.size(); t.assign(4*n+5, 0); build(1, 1, n); map<ll, vector<ll> > m; for(ll i = 0; i < n; i++) { m[v[i]].push_back(i+1); } ll res = 0; vector<pair<ll, ll> > pairs; for(ll i = 0; i < maxN; i++) { for(ll j = 0; j < (ll)m[i].size(); j++) { pairs.push_back({m[-i][j], m[i][j]}); if(m[-i][j] > m[i][j]) { res++; } } } sort(pairs.begin(), pairs.end()); for(auto p : pairs) { res += sum(1, 1, n, p.first+1, p.second-1); update(1, 1, n, p.second, 0); } return res; }
#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...