Submission #231206

#	Time	Username	Problem	Language	Result	Execution time	Memory
231206		UserIsUndefined	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	368 ms	31352 KiB

shoes

/**
 *    author:  Mohamad Milhem
 *    created: 2020-05-13-05.41.20
**/
#include "shoes.h"
#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define MOD ll(1000000007)
#define debug(x) cout << '[' << #x << " is: " << x << "] " <<endl;
#define decimalpoint cout << std::fixed << setprecision(5)

map<int,map<int,bool>> need;
int bro[200005];
int nothing[200005];
int seg[800005];



void update(int p , int s, int e, int i){
    if (s == e){
        seg[p] = 1;
        return;
    }


    if (i <= (s+e)/2) update(p*2 , s , (s+e)/2 , i);
    else update(p*2 + 1 , (s+e)/2 + 1 , e , i);

    seg[p] = seg[p*2] + seg[p*2 + 1];
}



ll gett(int p , int s , int e , int a , int b){
    if ((s >= a)&&(e <= b)){
        return seg[p];
    }
    if ((s > b)||(a > e)){
        return 0;
    }

    return gett(p*2 , s , (s+e)/2 , a , b) + gett(p*2 + 1 , (s+e)/2 + 1 , e , a , b);

}



long long count_swaps(std::vector<int> v) {
	ll n = v.size();
	need.clear();
    memset(bro, 0 , sizeof bro);
    memset(nothing , 0 , sizeof nothing);
    memset(seg , 0 , sizeof seg);

    for (int i = 0 ; i < n ; i++){
        int needed = v[i]*-1;
        auto here = need[needed].begin();
        if (here == need[needed].end()){
            need[v[i]][i] = true;
        }
        else {
            int first = here->first;
            int second = i;
            bro[first] = second;
            need[needed].erase(first);
        }
    }

    ll ans = 0;

//    for (auto a : bro){
//        cout << a.first << " " << a.second << endl;
//    }


    for (ll i = 0 ; i < n ; i++){
        ll now = v[i];

        if (bro[i] == 0)continue;

        ll cont = 0;

//        for (ll j = i + 1 ; j < bro[i] ; j++){
////            if (nothing[j])cont++;
//        }
        cont = gett(1 , 0 , n - 1 , i + 1 , bro[i] - 1);
//        debug(cont);
//        debug(i);
//        nothing[bro[i]] = 1;
        update(1 , 0, n - 1 , bro[i]);
        int leftt = (now < 0);

        ll here = bro[i] - i - leftt - cont;
//        debug(i);
//      debug(here);

        ans+= here;

    }

    return ans;
}

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