Submission #794564

#TimeUsernameProblemLanguageResultExecution timeMemory
794564Pablo_NoArranging Shoes (IOI19_shoes)C++17
100 / 100
88 ms17992 KiB
#include "shoes.h" #include <iostream> #include <set> using namespace std; const int N = 1e5+5; set<int> p[2*N]; int ft[2*N]; void add(int p, int v) { while(p < 2*N) { ft[p] += v; p += (p & (-p)); } } int rsq(int p) { int ans = 0; while(p) { ans += ft[p]; p -= (p & (-p)); } return ans; } long long count_swaps(std::vector<int> s) { long long ans = 0; for(int i = 0; i < s.size(); i++) { int ai = s[i]; if(!p[-ai+N].empty()) { int fp = *p[-ai+N].begin(); //cerr << rsq(fp+1) << '\n'; ans += (i-fp)-(ai > 0)-rsq(fp+1); add(fp+2, 1); add(i+1, -1); p[-ai+N].erase(fp); } else { p[ai+N].insert(i); } } return ans; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < s.size(); i++)
      |                 ~~^~~~~~~~~~
#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...