Submission #168994

#	Time	Username	Problem	Language	Result	Execution time	Memory
168994		pulpy_orange	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	114 ms	16400 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int mxn=200007;
int BIT[mxn];

void update(int index, int n, int val){
     while(index<=n){
          BIT[index]+=val;
          index+=index&-index;
     }
}

int query(int index){
     int sum=0;
     while(index>0){
          sum+=BIT[index];
          index-=index&-index;
     }
     return sum;
}


ll count_swaps(vector<int>S){
     int n=S.size();

     vector<int>L[100007], R[100007];

     for(int i=0;i<n;i++){
          if(S[i]<0){
               L[abs(S[i])].push_back(i);
          }
          else R[S[i]].push_back(i);
     }

     vector<int>M(n+1, 0);
     for(int i=1;i<=100007;i++){
          for(int j=0;j<L[i].size();j++){
               M[L[i][j]+1]=R[i][j]+1;
               M[R[i][j]+1]=L[i][j]+1;
          }
     }

     int vis[n+1];
     memset(vis, 0, sizeof(vis));
     ll ans=0;
     for(int i=1;i<M.size();i++){
          if(vis[i])continue;
          int cnt=query(M[i])-query(i);
          if(S[i-1]>0){
               ans+=(M[i]-i)-cnt;
          }
          else{
               ans+=(M[i]-i-1)-cnt;
          }
          vis[M[i]]=1;
          update(M[i], n, 1);
     }

     return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(int j=0;j<L[i].size();j++){
                       ~^~~~~~~~~~~~
shoes.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=1;i<M.size();i++){
                  ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15