Submission #1203822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203822		Aviansh	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	616 ms	148068 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

struct segTree{
    int *st;
    int n;
    segTree(int siz){
        int x = ceil(log2(siz));
        x++;
        st=new int[(1<<x)];
        fill(st,st+(1<<x),0);
        n=siz-1;
        for(int i = 0;i<siz;i++){
            update(i,1);
        }
    }

    void rupdate(int l, int r, int i, int val, int ind){
        if(i<l||i>r){
            return;
        }
        if(l==r){
            st[ind]=val;
            return;
        }
        int mid = (l+r)/2;
        rupdate(l,mid,i,val,2*ind+1);
        rupdate(mid+1,r,i,val,2*ind+2);
        st[ind]=st[ind*2+1]+st[ind*2+2];
    }

    void update(int i, int val){
        rupdate(0,n,i,val,0);
    }

    int rquery(int l, int r, int s, int e, int ind){
        if(e<l||s>r){
            return 0;
        }
        if(s<=l&&r<=e){
            return st[ind];
        }
        int mid = (l+r)/2;
        return rquery(l,mid,s,e,ind*2+1)+rquery(mid+1,r,s,e,ind*2+2);
    }

    int query(int l, int r){
        return rquery(0,n,l,r,0);
    }
};

long long count_swaps(vector<int> s) {
    long long ans = 0;
    int n = s.size();
    map<int,queue<int>>mp;
    for(int i = 0;i<n;i++){
        mp[s[i]].push(i);
    }
    segTree st(n);
    for(int i = 0;i<n;i++){
        if(st.query(i,i)==0)
            continue;
        int ind = mp[-s[i]].front();
        mp[-s[i]].pop();
        mp[s[i]].pop();
        st.update(i,0);
        if(s[i]<0){
            ans+=st.query(i,ind)-1;
        }
        else{
            ans+=st.query(i,ind);
        }
        st.update(ind,0);
    }
	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