Submission #171363

#TimeUsernameProblemLanguageResultExecution timeMemory
171363XellosArranging Shoes (IOI19_shoes)C++17
100 / 100
156 ms15880 KiB
#include "shoes.h" class fin { std::vector<int> T; int lastone(int x) { return x & (x ^ (x-1)); } public: fin(int N) : T(N+1, 0) {} void put(int pos, int val) { for(int i = pos+1; i < (int)T.size(); i += lastone(i)) T[i] += val; } int get(int pos) { int ret = 0; for(int i = pos+1; i > 0; i -= lastone(i)) ret += T[i]; return ret; } }; long long count_swaps(std::vector<int> S) { int N = S.size()/2; std::vector<int> pos_l[100010], pos_r[100010]; for(int i = 0; i < 2*N; i++) { if(S[i] < 0) pos_l[-S[i]].push_back(i); else pos_r[S[i]].push_back(i); } long long ret = 0; std::vector<int> next(2*N, 0); for(int i = 1; i <= N; i++) for(int j = 0; j < (int)pos_l[i].size(); j++) next[std::min(pos_l[i][j], pos_r[i][j])] = std::max(pos_l[i][j], pos_r[i][j]); fin F(2*N); for(int i = 0; i < 2*N; i++) F.put(i, 1); std::vector<char> live(2*N, 1); for(int i = 0; i < 2*N; i++) if(next[i]) { ret += F.get(next[i]-1) - F.get(i); F.put(next[i], -1); } for(int i = 1; i <= N; i++) for(int j = 0; j < (int)pos_l[i].size(); j++) if(pos_l[i][j] > pos_r[i][j]) ret++; 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...