Submission #1070048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070048		j_vdd16	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	86 ms	27656 KiB

shoes

#include "shoes.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

struct SegTree {
    int n, N;

    vi tree;
    SegTree(const vi& values) {
        n = values.size();
        N = 1;

        while (N < n) N *= 2;

        tree = vi(2 * N);
        loop(i, n) {
            tree[N + i] = values[i];
        }
        for (int i = N - 1; i >= 1; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    void set(int idx, int v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) {
            tr = N;
        }

        if (tr - tl == 1) {
            tree[i] = v;
            return;
        }

        int tm = (tl + tr) / 2;
        if (idx < tm) {
            set(idx, v, 2 * i, tl, tm);
        }
        else {
            set(idx, v, 2 * i + 1, tm, tr);
        }

        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    int get(int idx) {
        return tree[N + idx];
    }

    int getRange(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) {
            tr = N;
        }

        if (tr <= l || tl >= r) {
            return 0;
        }

        if (tl >= l && tr <= r) {
            return tree[i];
        }

        int tm = (tl + tr) / 2;
        return getRange(l, r, i * 2, tl, tm) + getRange(l, r, i * 2 + 1, tm, tr);
    }
};

long long count_swaps(std::vector<signed> s) {
    int n = s.size();
    vector<pair<vi, vi>> positions(n);
    loop(i, n) {
        if (s[i] < 0) {
            positions[-s[i]].first.push_back(i);
        }
        else {
            positions[s[i]].second.push_back(i);
        }
    }
    vii ptrs(n);

    int result = 0;
    SegTree isUsed(vi(n, false));
    for (int i = 0; i < n; i++) {
        if (isUsed.get(i)) continue;

        int v = s[i];
        int next;
        if (v < 0) {
            next = positions[-v].second[ptrs[-v].second];
            ptrs[-v].first++;
            ptrs[-v].second++;
        }
        else {
            next = positions[v].first[ptrs[v].first];
            ptrs[v].first++;
            ptrs[v].second++;
        }

        int count = (next - i - 1) - isUsed.getRange(i + 1, next + 1);
        // for (int j = i + 1; j < n; j++) {
        //     if (s[j] == -v && !isUsed.get(j)) {
        //         isUsed.set(j, true);
        //         break;
        //     }

        //     count += 1 - isUsed.get(j);
        // }

        if (v < 0) {
            result += count;
        }
        else {
            result += count + 1;
        }
        isUsed.set(next, true);
        isUsed.set(i, true);
    }

	return result;
}

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