Submission #850064

#TimeUsernameProblemLanguageResultExecution timeMemory
850064Bach21Arranging Shoes (IOI19_shoes)C++14
100 / 100
70 ms12832 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; const int nmax=2e5+5; int BIT[nmax]; void update(int s,int val) { for (int i=s;i<nmax;i+=i&-i) { BIT[i]+=val; } } int query(int s) { int res=0; for (int i=s;i;i-=i&(-i)) { res+=BIT[i]; } return res; } long long count_swaps(vector<int> s) { long long res=0; int n=(int)(s.size()/2); vector<pair<int,int>> v[nmax]; for (int i=0;i<s.size();i++) { v[abs(s[i])].push_back({s[i],i}); } vector<pair<int,int>> xl; for (int i=1;i<=n;i++) { sort(v[i].begin(),v[i].end()); for (int j=0;j<(v[i].size()/2);j++) { int l=v[i][j].second; int r=v[i][j+(int)(v[i].size()/2)].second; if (l>r) { swap(l,r); res++; } xl.push_back({l+1,r+1}); } } for (int i=1;i<=n*2;i++) { update(i,1); } sort(xl.begin(),xl.end()); for (auto x : xl) { res+=query(x.second-1)- query(x.first); update(x.first,-1); update(x.second,-1); } return res; }

Compilation message (stderr)

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