Submission #959455

#	Time	Username	Problem	Language	Result	Execution time	Memory
959455		NemanjaSo2005	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	347 ms	152040 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
ll N,niz[maxn],par[maxn];
ll res=0;
map<int,queue<int>> mapa;
ll fwt[maxn];
void add(int x,int kol){
   for(int i=x;i<=N;i+=(i&(-i)))
      fwt[i]+=kol;
}
ll get(int x){
   if(x<1)
      return 0;
   ll ret=0;
   for(int i=x;i>=1;i-=(i&(-i)))
      ret+=fwt[i];
   return ret;
}
ll suma(ll l,ll r){
   if(l>r)
      return 0;
  // cout<<l<<" "<<r<<" "<<get(l-1)<<" "<<get(r)<<endl;
   return get(r)-get(l-1);
}
ll count_swaps(vector<int> s) {
	N=s.size();
	for(int i=0;i<N;i++)
      niz[i+1]=s[i];
   for(int i=1;i<=N;i++){
      int sup=-niz[i];
      if(mapa[sup].size()!=0){
         int x=mapa[sup].front();
         mapa[sup].pop();
         par[x]=i;
         par[i]=x;
         continue;
      }
      mapa[niz[i]].push(i);
   }
   for(int i=1;i<=N;i++){
      if(niz[i]==0)
         continue;
      if(niz[i]>0) /// Zamena leva-desna na kraju
         res++;
      //cout<<i<<" "<<par[i]<<endl;
      res+=(par[i]-i-1);
      //cout<<suma(i+1,par[i]-1)<<endl;
      res-=suma(i+1,par[i]-1);

      add(i,1);
      add(par[i],1);
      niz[i]=0;
      niz[par[i]]=0;
   }
   return res;
}

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