Submission #1350787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350787		feyza	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

typedef long long ll;

struct SegTree {
    int n;
    vector<int> tree;

    SegTree(int n) : n(n), tree(4*n, 0) {}

    void build(int node, int l, int r) {
        if (l == r) {
            tree[node] = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    void update(int node, int l, int r, int pos) {
        if (l == r) {
            tree[node] = 0;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2*node, l, mid, pos);
        else update(2*node+1, mid+1, r, pos);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return query(2*node, l, mid, ql, qr) +
               query(2*node+1, mid+1, r, ql, qr);
    }
};

ll solve8(vector<int> &s)
{
    int n = s.size();

    // positions of each value
    unordered_map<int, deque<int>> pos;
    for (int i = 0; i < n; i++)
        pos[s[i]].push_back(i);

    SegTree st(n);
    st.build(1, 0, n-1);

    vector<bool> removed(n, false);

    ll ans = 0;

    for (int i = 0; i < n; i++)
    {
        if (removed[i]) continue;

        int x = s[i];
        pos[x].pop_front();

        // find first alive occurrence of -x
        while (!pos[-x].empty() && removed[pos[-x].front()])
            pos[-x].pop_front();

        int j = pos[-x].front();
        pos[-x].pop_front();

        // number of active elements strictly between i and j
        int swaps = st.query(1, 0, n-1, i+1, j-1);

        ans += swaps;

        // same correction as your code
        if (x > 0)
            ans++;

        // remove both
        st.update(1, 0, n-1, i);
        st.update(1, 0, n-1, j);

        removed[i] = removed[j] = true;
    }

    return ans;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc4lhKuc.o: in function `main':
grader.cpp:(.text.startup+0x26b): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status