Submission #1216909

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

shoes

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define REP(a,i,n) for (int i=a;i<n;i++)

vector<queue<int> > saan(400'005);

struct SegTree {
    int l, r, val;
    SegTree* lt, * rt;

    void combine() {
        val = lt->val + rt->val;
    }

    SegTree(int left, int right, vector<int>& a) {
        l = left; r = right;
        lt = rt = nullptr;

        if (left==right) {
            val = a[left];
            return;
        }

        int mid = (l+r)>>1;
        lt = new SegTree(l, mid, a);
        rt = new SegTree(mid+1, r, a);
        combine();
    }

    void update(int i){
        if(l <= i && i <= r){
            if (lt) {
                lt->update(i);
                rt->update(i);
                combine();
            }
            else {
                val++;
            }
        }
    }

    int query(int ql, int qr) {
        if (qr < l || r < ql) { // completely out
            return 0;
        }
        if ( ql <= l && r <= qr) { //completely in
            return val;
        }
        return lt->query(ql, qr) + rt->query(ql, qr);
    }
};


int count_swaps(vector<int> S) {
    vector<int> arr;
    int N=S.size(), ind=0, count=0;
    for (int shoe : S) {
        if (saan[shoe + 200'000].empty()) {
            saan[-shoe + 200'000].push(ind + (shoe < 0)); //push the opposite
            arr.push_back(ind + (shoe > 0));
            ind += 2;
        }
        else {
            arr.push_back(saan[shoe + 200'000].front());
            saan[shoe + 200'000].pop();
        }
    }
    vector<int> ex(ind, 0);
    SegTree* sgt = new SegTree(0, ind-1, ex);
    for (int i=N-1; i>=0;i--) {
        count += sgt->query(0, arr[i]-1);
        sgt->update(arr[i]);
    }

    return count;
}

int main() {
    vector<int> s = {2, -2, 2, -2, -2, -2, 2, 2};
    cout << count_swaps(s);
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc1EqZ4z.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccwoWMYe.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status