Submission #602985

#	Time	Username	Problem	Language	Result	Execution time	Memory
602985		definitelynotmee	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	74 ms	20372 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using matrix = vector<vector<T>>;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

template<typename T>
struct smartvec{
    vector<T> v;
    int n;
    smartvec(int sz = 0){
        n = sz;
        v = vector<T>(2*sz+1);
    }

    T& operator[](int id){
        return v[id+n];
    }

};  

long long count_swaps(std::vector<int> v) {
    
    int n = v.size();
    ll resp = 0;
    vector<int> bit(n+1);
    auto update=[&](int id, int val){
        id++;
        while(id<=n){
            bit[id]+=val;
            id+=id&-id;
        }
    };

    auto query =[&](int id){
        id++;
        int ret = 0;
        while(id){
            ret+=bit[id];
            id-=id&-id;
        }
        return ret;
    };

    smartvec<vector<int>> ocur(n);

    for(int i = n-1; i >= 0; i--){
        update(i,1);
        ocur[v[i]].push_back(i);
    }
    vector<int> passed(n);

    for(int i = 0; i < n; i++){
        if(passed[i])
            continue;
        
        ocur[v[i]].pop_back();
        update(i,-1);

        int next = ocur[v[i]*-1].back();
        ocur[v[i]*-1].pop_back();
        update(next,-1);
        
        passed[i] = 1;
        passed[next] = 1;

        resp+=query(next);
        resp+=v[i]> 0;
    }
    

    return resp;
}

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