Submission #1226385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226385		alexaaa	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	235 ms	27032 KiB

shoes

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<climits>
using namespace std;

vector<int> st(600000,0);

void add(int index, int r_begin, int r_end, int x){
    if(r_begin == r_end && r_begin == x){
        st[index] ++;
        return;
    }
    int mid = (r_begin+r_end)/2;
    if(x <= mid){
        add(index*2+1, r_begin, mid, x);
    }
    else {
        add(index*2+2,mid+1,r_end,x);
    }
    st[index]=st[index*2+1]+st[index*2+2];
    return;


}

int query(int index, int r_begin, int r_end, int l, int r){
   
    if(l <= r_begin && r_end <= r){
        return st[index];

    }
    if(r_end < l || r_begin > r){
        return 0;

    }
    int mid = (r_begin + r_end)/2;
    return query(index*2+1,r_begin,mid,l,r) + query(index*2+2,mid+1,r_end,l,r);
}

long long count_swaps(vector<int> S){
    int n = S.size();
    vector<int> seen(n,0);
    map<int, priority_queue<int, vector<int>, greater<int>>> positive, negative;

    for(int i = 0; i < n; i++){
        if(S[i] < 0){
            negative[abs(S[i])].push(i); 
        }
        else{
            positive[S[i]].push(i);
        }

    }
    long long res = 0;
    int pos;
    for(int j = 0; j < n; j ++){
        if(!seen[j]){
            if(S[j] > 0){
                pos = negative[S[j]].top();
            }
            else{
                pos = positive[abs(S[j])].top();
                
            }
            negative[abs(S[j])].pop();
            positive[abs(S[j])].pop();

            res += abs(j - pos)-1;
            res -= query(0,0,n-1,j+1,pos);
            if(S[j]>0){
                res ++;
            } 
            seen[pos]=1;
            add(0,0,n-1,pos);


            
        }
    }
    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