Submission #488074

#	Time	Username	Problem	Language	Result	Execution time	Memory
488074		ala2	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	197 ms	31700 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int b[1000100];
int a[1000100];
int seg[4*1001000];
void sett(int s,int e,int p,int l,int r)
{
   // cout<<"        ?    "<<endl;
    if(l>e||r<s)
        return ;
    if(s>=l&&e<=r)
    {
        seg[p]++;
        return ;
    }
    int mid=(s+e)/2;
    sett(s,mid,p*2,l,r);
    sett(mid+1,e,p*2+1,l,r);

    return ;
}
int gett(int s,int e,int p,int i)
{
    //cout<<"          !   "<<endl;
    if(i<s||i>e)
        return 0;
    if(s==e)
          return seg[p];
    int mid=(s+e)/2;
    if(i>=s&&i<=mid)
        return gett(s,mid,p*2,i)+seg[p];

    else if(i>mid&&i<=e)
    {
        return gett(mid+1,e,p*2+1,i)+seg[p];
    }
    else return gett(mid+1,e,p*2+1,i)+seg[p]+gett(s,mid,p*2,i);


}
map<int,int>m;
vector<int>v[200100];
vector<int>v2[200100];
int vis[1001000];
long long count_swaps(vector<int> s) {

    int n=s.size();
    for(int i=0;i<n;i++)
    {
        a[i]=s[i];
    }
    for(int i=0;i<n;i++)
    {//cout<<"SD";
        if(a[i]>0)
        v[a[i]].push_back(i);
        else
            v2[-a[i]].push_back(i);

    } long long mn=0;
    for(int i=0;i<n;i++)
    {
        if(vis[i])
            continue;
        if(a[i]<0)
        {
            int ii=gett(0,n-1,1,i);
            ii+=i;
            int y=m[-a[i]];
            int jj=v[-a[i]][y];
            int jjj=jj;
            vis[jj]=1;
            jj+=gett(0,n-1,1,jj);
            m[-a[i]]++;
            m[a[i]]++;
            mn+=jj-ii-1;
            sett(0,n-1,1,i,jjj-1);
           // cout<<"             "<<ii<<"  "<<jj<<" "<<i<<endl;


        }
        else {
        int ii=gett(0,n-1,1,i);
            ii+=i;
        int y=m[-a[i]];
        int jj=v2[a[i]][y];

        int jjj=jj;
            vis[jj]=1;
            jj+=gett(0,n-1,1,jj);
            m[-a[i]]++;
            m[a[i]]++;
            mn+=jj-ii;
            sett(0,n-1,1,0,jjj-1);
          //  cout<<"           "<<ii<<"  "<<jj<<endl;
        }
       // cout<<"             "<<mn<<endl;
    }
   // cout<<gett(0,n-1,1,0)<<endl;
return mn;

}
// 4 1 -2 -3 4 2 -1 -4 3

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