Submission #399314

#TimeUsernameProblemLanguageResultExecution timeMemory
399314_Avocado_Arranging Shoes (IOI19_shoes)C++14
45 / 100
696 ms95660 KiB
#include <bits/stdc++.h> #include <iostream> using namespace std; #define int int64_t vector<int>seg; void update(int k, int v, int pos, int l, int r){ if(l == r){ seg[pos] = v; return; } else if(k <= (l+r)/2) update(k, v, pos*2, l, (r+l)/2); else update(k, v, pos*2+1, (l+r)/2+1, r); seg[pos] = seg[pos*2] + seg[pos*2+1]; } int query(int ql, int qr, int pos, int l, int r){ if(l >= ql && r <= qr) return seg[pos]; else if(l > qr || r < ql) return 0; else return query(ql, qr, pos*2, l, (l+r)/2) + query(ql, qr, pos*2+1, (l+r)/2+1, r); } int solve(vector<int>&shoes, int n){ vector<vector<int>>fred(n); seg.assign(n*4, 0); for(int i = 0; i<n; ++i){ fred[i] = {shoes[i], i}; } sort(fred.begin(), fred.end()); reverse(fred.begin(), fred.end()); int ans = 0; for(int i = 0; i<n; ++i){ ans += query(0, fred[i][1]-1, 1, 0, n-1); update(fred[i][1], 1, 1, 0, n-1); } return ans; } long long count_swaps(std::vector<int32_t>v){ int n = v.size(); map<int, queue<int>>mp; vector<int>shoes1(n); int cur = 1; for(int i = 0; i<n; ++i){ if(v[i] < 0){ mp[v[i]].push(cur); shoes1[i] = cur; cur += 2; } } for(int i = 0; i<n; ++i){ if(v[i] > 0){ shoes1[i] = mp[-v[i]].front()+1; mp[-v[i]].pop(); } } vector<int>shoes2(n); mp.clear(); cur = 2; for(int i = 0; i<n; ++i){ if(v[i] > 0){ mp[v[i]].push(cur); shoes2[i] = cur; cur += 2; } } for(int i = 0; i<n; ++i){ if(v[i] < 0){ shoes2[i] = mp[-v[i]].front()-1; mp[-v[i]].pop(); } } /* for(auto u: shoes1) cout<<u<<" "; cout<<endl; for(auto u: shoes2) cout<<u<<" "; cout<<endl; */ int one = solve(shoes1, n); int two = solve(shoes2, n); return min(one, two); }
#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...