Submission #717330

#	Time	Username	Problem	Language	Result	Execution time	Memory
717330		Dakto	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	478 ms	154140 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

struct segtree{
    vector<int> val;
    vector<int> left, right;
    int n;

    segtree(int _n){
        n=1;
        while(n<_n) n*=2;

        val.resize(2*n);
        left.resize(2*n);
        right.resize(2*n);

        for(int i=0; i<n; i++){
            left[n+i]=right[n+i]=i;
        }
        for(int i=n-1; i>0; i--){
            left[i]=left[2*i];
            right[i]=right[2*i+1];
        }
    }
    void set(int ind, int vl){
        ind+=n;
        val[ind]=vl;
        ind/=2;
        while(ind>0){
            val[ind]=val[ind*2]+val[ind*2+1];
            ind/=2;
        }
    }
    int query(int l, int r, int x=1){
        if(l>r) return 0; 
        if(l>right[x] || r<left[x]) return 0;
        if(l<=left[x] && right[x]<=r) return val[x];
        return query(l,r,2*x)+query(l,r,2*x+1);
    }
};

long long count_swaps(std::vector<int> s) {
    map<int,queue<int>> m;

    vector<int> arr;
    int ctr=0;
    for(auto i:s){
        if(m[i].size()>0){
            arr.push_back(m[i].front());
            m[i].pop();
        }
        else{
            arr.push_back(2*ctr+(-i<0));
            m[-i].push(2*ctr+(i<0));
            ctr++;
        }
    }
    segtree tree(s.size());
    long long res=0;

    for(auto i:arr){
        tree.set(i, 1);
        res+=tree.query(i+1, s.size()-1);
    }
    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