Submission #1244333

#TimeUsernameProblemLanguageResultExecution timeMemory
1244333superomegoArranging Shoes (IOI19_shoes)C++20
25 / 100
115 ms29884 KiB
#include <bits/stdc++.h> using namespace std; void fwt(long long s, long long i, vector<long long> &v, vector<long long> &f){ if(i >= v.size()) return; if(i > 0) for(int di = -s+1; di < 1; ++di) f[i] += v[i+di]; else f[0] = v[0]; int c = i, inc = 1; while(inc < s){ fwt(inc, c+inc, v, f); inc = inc << 1; } return; } long long getpref(int i, int j, vector<long long> &f){ if(i > 0) return getpref(0, j, f) - getpref(0, i-1, f); long long res = f[0]; int k = j, inc = 1; while(k > 0){ if(k & inc){ res += f[k]; k -= inc; } inc = inc << 1; } return res; } void setpref(int i, long long v, vector<long long> &vi, vector<long long> &fwt){ if(i == 0){ fwt[0] = v; return; } int dt = v - vi[i], nx = i, lsb = 1; vi[i] = v; while(nx < fwt.size()){ fwt[nx] += dt; while(not (nx & lsb)) lsb = lsb << 1; nx += lsb; } } long long count_swaps(vector<int> S){ long long n = S.size(), ret = 0; unordered_map<int, pair<vector<long long>, vector<long long>>> v; set<tuple<long long, long long, long long>> s; vector<long long> pref(2*n, 0); vector<long long> ofwt(2*n, 0); for(int i = 0; i < S.size(); ++i){ if(v.find(abs(S[i])) == v.end()) v[abs(S[i])] = {vector<long long>(), vector<long long>()}; if(S[i] < 0) v[-S[i]].first.push_back(i); else v[S[i]].second.push_back(i); } for(auto &[k, w] : v){ auto it1 = w.first.rbegin(), it2 = w.second.rbegin(); while(it1 != w.first.rend()){ if((*it1) > (*it2)) s.insert({(*it1), (*it2), 0}); else s.insert({(*it2), (*it1), -1}); it1++; it2++; } } for(auto it = s.rbegin(); it != s.rend(); ++it){ long long val = getpref(get<1>(*it), 2*n - 1, ofwt); ret += get<0>(*it) + get<2>(*it) - get<1>(*it) - val; setpref(get<1>(*it), 1, pref, ofwt); } return ret; }
#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...