Submission #1209828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209828		ASGA_RedSea	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 KiB

shoes

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

long long count_swaps(vector<int>s);

struct ft{
    vector<ll>f;
    int n;
    ft(int N){
        n=N+1;
        f.assign(n+1,0);
        for(int i=1;i<=n;i++){
            int j=i;
            while(j<=n){
                f[j]++;
                j+=j&-j;
            }
        }
    }

    void edit(int i){
        i++;
        while(i<=n){
            f[i]++;
            i+=i&-i;
        }
    }
    int get(int i){
        ll ret=0;i++;
        while(i){
            ret+=f[i];
            i-=i&-i;
        }
        return ret;
    }
};

ll count_swaps(vector<int>a){
    int n=a.size();
    ll ans=0;

    ft f(n);

    vector<array<vector<int>,2>>pos(n/2+1);
    for(int i=0;i<n;i++)pos[abs(a[i])][a[i]<0].push_back(i);

    vector<array<int,2>>rng;

    vector<int>vis(n,0);
    for(int i=0;i<n;i++){
        if(vis[i])continue;

        int j=pos[abs(a[i])][a[i]>0].back();
        pos[abs(a[i])][a[i]>0].pop_back();


        vis[j]=1;

        rng.push_back({j,i});
    }

    sort(rng.rbegin(),rng.rend());
    for(auto&[j,i]:rng){
        if(a[i]<0)ans+=f.get(j-1)-f.get(i);
        else ans+=f.get(j)-f.get(i);
        f.edit(j);
    }

    return ans;
}

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