Submission #491340

#	Time	Username	Problem	Language	Result	Execution time	Memory
491340		Carmel_Ab1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	637 ms	43608 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int>pi;

#define pb push_back
#define print(x) {for(auto it:x)cout << it << " " ; cout << "\n";}
struct seg{
    int sz=1;
    vi t;

    seg(int n){
        while(sz<=2*n)
            sz*=2;
        t.resize(sz);
    }

    void upd(int i,int v){
        t[i+=sz/2]+=v;
        while(i){
            t[i/2]=t[i]+t[i^1];
            i/=2;
        }
    }
    int qur(int l,int r){
        int ans=0;
        for(l+=sz/2,r+=sz/2 +1; l<r; l/=2,r/=2){
            if(l&1)ans+=t[l++];
            if(r&1)ans+=t[--r];
        }
        return ans;
    }
};
ll count_swaps(vi a){
    ll n=a.size()/2,ans=0;

    vi to(2*n);

    set<pi>s;
    map<int,set<int>>where;

    for(int i=0; i<2*n; i++) {
        s.insert({i, a[i]});
        where[a[i]].insert(i);
    }

    int seen=0;
    while(s.size()){
        pi p1=*s.begin();
        s.erase(p1);
        int i=p1.first;

        int j=*where[-p1.second].upper_bound(i);
        s.erase({j,a[j]});

        where[a[j]].erase(j);
        where[a[i]].erase(i);

        if(a[i]>a[j])
            to[i]=2*seen+1,to[j]=2*seen;
        else
            to[i]=2*seen,to[j]=2*seen+1;
        seen++;
    }

    seg ST(2*n);
    for(int i=0; i<2*n; i++) {
        ans+=ST.qur(to[i]+1,2*n-1);
        ST.upd(to[i],1);
    }
    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