Submission #433194

#TimeUsernameProblemLanguageResultExecution timeMemory
433194kostia244Arranging Shoes (IOI19_shoes)C++17
10 / 100
1 ms204 KiB
#include "shoes.h" #include<bits/stdc++.h> using namespace std; using ll = long long; #define all(x) begin(x), end(x) long long count_swaps(std::vector<int> s) { int n = s.size()/2; ll res = 0; for(auto &i : s) i = 2*abs(i) + (i>0); vector<array<int, 2>> b; for(int i = 0; i < 2*n; i++) b.push_back({s[i], i+1}); sort(all(b)); vector<ll> fen(2*n+1); auto add = [&](int x) { for(; x <= 2*n; x += x&-x) fen[x]++; }; auto get = [&](int x) { int res = 0; add(x); for(; x; x -= x&-x) res += fen[x]; return res; }; int cur = 0; for(auto [_, i] : b) { res += ++cur - get(i); } 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...