Submission #1284647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284647		Rares	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	48 ms	14516 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
/**ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout*/

typedef long long ll;
const int MAXN=2e5+10;

int n;
bool ok[MAXN];
ll rez;
vector <int> v;
vector <int> ap[2][MAXN];
int aib[MAXN];

void update (int pos, int val){
    for (int i=pos;i<=n;i+=(i&(-i)))aib[i]+=val;
}

void update (int l, int r, int val){
    update (l,val);
    update (r+1,-val);
}

int query (int pos){
    int rez=0;
    for (int i=pos;i>0;i-=(i&(-i))) rez+=aib[i];
    return rez;
}

int query (int l,int r){
    return query (r)-query (l-1);
}


ll count_swaps (vector <int> aux){

    n=aux.size ();
    v.resize (n+1);
    for (int i=0;i<n;++i){
        v[i+1]=aux[i];
    }

    for (int i=n;i>=1;--i){
        if (v[i]<0) ap[0][-v[i]].push_back (i);
        else ap[1][v[i]].push_back (i);
    }


    for (int i=1;i<=n;++i){
        if (ok[i]) continue;
        int crt=v[i],pos=0;
        if (crt<0){
            pos=ap[1][-crt].back ();
            ap[1][-crt].pop_back ();
            ap[0][-crt].pop_back ();
        }
        else{
            rez++;

            pos=ap[0][crt].back ();
            ap[0][crt].pop_back ();
            ap[1][crt].pop_back ();
        }
        ok[pos]=1;
        int l=i+query (i+1,n),r=pos+query (pos+1,n);
        rez+=r-l-1;

        update (pos,1);
        //cout <<l<<' '<<r<<'\n';
    }
    return rez;
}

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