Submission #1080081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080081		Icelast	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	133 ms	24592 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct SegmentTree{
    vector<ll> T;
    int n, N;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1, 0);
    };
    void upd(int i, int x){
        auto upd = [&](auto upd, int node, int low, int high, int i, int x) -> void{
            if(low == high){
                T[node] = x;
                return;
            }
            int mid = (low+high)/2;
            if(i <= mid){
                upd(upd, node*2, low, mid, i, x);
            }else{
                upd(upd, node*2+1, mid+1, high, i, x);
            }
            T[node] = T[node*2]+T[node*2+1];
        };
        upd(upd, 1, 1, N, i, x);
    }
    int sum(int l, int r){
        auto sum = [&](auto sum, int node, int low, int high, int l, int r) -> int{
            if(low > r || l > high) return 0;
            if(low >= l && r >= high) return T[node];
            int mid = (low+high)/2;
            return sum(sum, node*2, low, mid, l, r) + sum(sum, node*2+1, mid+1, high, l, r);
        };
        return sum(sum, 1, 1, N, l, r);
    }
};
long long count_swaps(std::vector<int> s) {
    int n = s.size();
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++){
        a[i] = s[i-1];
    }
    vector<vector<int>> d(n+1), c(n+1);
    for(int i = n; i >= 1; i--){
        if(a[i] < 0){
            c[a[i]*-1].push_back(i);
        }else{
            d[a[i]].push_back(i);
        }
    }

    vector<bool> alive(n+1, 1);
    ll ans = 0;
    SegmentTree T(n+1);
    for(int i = 1; i <= n; i++){
        T.upd(i, 1);
    }
    for(int i = 1; i <= n; i++){
        if(!alive[i]) continue;
        if(a[i] < 0){
            c[a[i]*-1].pop_back();

            int j = d[a[i]*-1].back();
            d[a[i]*-1].pop_back();
            ans += T.sum(i+1, j)-1;
            alive[i] = 0;
            T.upd(i, 0);
            alive[j] = 0;
            T.upd(j, 0);
        }else{
            d[a[i]].pop_back();

            int j = c[a[i]].back();
            c[a[i]].pop_back();
            ans += T.sum(i, j)-1;
            alive[i] = 0;
            T.upd(i, 0);
            alive[j] = 0;
            T.upd(j, 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