Submission #1321520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321520		spetr	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	332 KiB

shoes

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

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>


void build(ll l, ll r, ll i, vl& tree){
    if (l == r){
        tree[i] = 1;
        return;
    }
    ll mid = (l+r)/2;
    build(l, mid, 2*i, tree);
    build(mid+1, r, 2*i+1, tree);
    tree[i] = tree[2*i] + tree[2*i+1];
    return;
}

void update(ll l, ll r, ll p, ll i, vl& tree){
    if (l == p && r == p){
        tree[i] = 0;
        return;
    }
    if (p < l || r < p){
        return;
    }
    ll mid = (l+r)/2;
    update(l, mid, p, 2*i, tree);
    update(mid+1, r, p, 2*i+1, tree);
    tree[i] = tree[2*i] + tree[2*i+1];
    return;
}

ll query(ll l, ll r, ll L, ll R, ll i, vl& tree){
    if (L <= l && r <= R){
        return tree[i];
    }
    if (r < L || R < l){
        return 0;
    }
    ll mid = (l+r)/2;
    ll a = query(l, mid, L, R, 2*i, tree);
    ll b = query(mid+1, r, L, R, 2*i+1, tree);
    return a + b;
}

ll count_swaps(vector<int> S){
    ll n = S.size();

    vl nums;
    for (ll i = 0; i < n; i++){nums.push_back(S[i]);}

    vll occ (n/2+1);
    vl pairs (n);
    for (ll i = 0; i < n; i++){
        ll p = abs(nums[i]);
        if (occ[p].empty()){
            occ[p].push_back(i);
            continue;
        }
        if (nums[occ[p][occ[p].size() -1]] == nums[i]){
            occ[p].push_back(i);
        }
        else{
            ll pos = occ[p][occ[p].size() - 1];
            pairs[pos] = i;
            pairs[i] = pos;
            occ[p].pop_back();
        }
    }

    vl tree (4*n + 4, 0);
    ll s = 1;
    while (s < n){
        s *= 2;
    }
    s--;
    build(0, s, 1, tree);

    ll suma = 0;
    for (ll i = 0; i < n; i++){
        ll j = pairs[i];
        if (j-1 > i){
            suma += query(0, s, i+1, j-1, 1, tree);
            if (nums[i] < 0){
                suma++;
            }
        }
        update(0,s,j,1, tree);
    }
    return suma;
}

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