Submission #689926

#	Time	Username	Problem	Language	Result	Execution time	Memory
689926		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include <bits/stdc++.h>

#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9

using namespace std;

int n;
vector<int> tree;

void update(int pos, int val){
    while(pos < n){
        tree[pos] += val;
        pos += (pos & (-pos));
    }
}

int ask(int l, int r){
    if(l > r) return 0;
    if(l != 1) return ask(1, r) - ask(1, l - 1);
    int ans = 0;
    while(r > 0){
        ans += tree[r];
        r -= (r & (-r));
    }
    return ans;
}

ll count_swaps(int N, int S[]){
    n = N;
    tree.resize(n + 1);
    fill(tree.begin(), tree.end(), 0);

    map<int, set<int>> mp;
    for (int i = 0; i < n; i++)
    {
        update(i + 1, 1);
        mp[S[i]].insert(i + 1);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if(S[i - 1] > 0){
            set<int> &s = mp[-S[i - 1]];
            auto itr1 = s.upper_bound(i);
            auto itr2 = itr1;

            int dif1 = oo, dif2 = oo;
            if(itr1 != s.end()){
                dif1 = ask(i, (*itr1) - 1);
            }
            if(itr1 != s.begin()){
                itr2 = prev(itr2);
                dif2 = ask((*itr2) + 1, i - 1);
            }
            if(dif1 <= dif2){
                update(i, 1);
                update(*itr1, - 1);
                ans += dif1;
                s.erase(itr1);
            }
            else{
                update(i, 1);
                update(*itr2, -1);
                ans += dif2;
                s.erase(itr2);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

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