Submission #1213017

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

shoes

#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;

struct SeggsTree{
    SeggsTree *l = 0, *r = 0;
    int low, high;

    struct Data{
        int value;
        Data() {value = 0;}
        Data(int v) {value = v;}
        void update(int a) {value += a;}
        static Data merge(Data a, Data b){return Data(a.value + b.value);} 
    };

    Data d;

    SeggsTree(vector<int> &arr, int L, int R){
        low = L, high = R;
        if(R-L <= 1){
            d = Data(arr[L]);
            return;
        }

        int mid = (high + low) / 2;
        l = new SeggsTree(arr, L, mid);
        r = new SeggsTree(arr, mid, R);

        d = Data::merge(l->d, r->d); 
    }

    ~SeggsTree(){
        if(!l) return;
        delete l;
        delete r;
    }

    int lazy = 0;

    void push(){
        if(lazy == 0) return;
        if(!l) return;
        l->d.update(lazy);
        l->lazy = lazy;
        r->d.update(lazy);
        r->lazy = lazy;
        lazy = 0;
    }

    Data query(int L, int R){
        if(R <= low || high <= L) return Data(0);
        if(L <= low && high <= R) return d;
        push();
        return Data::merge(l->query(L, R), r->query(L, R));
    }

    void update(int v, int L, int R){
        if(R <= low || high <= L) return;
        if(L <= low && high <= R){
            d.update(v);
            lazy += v;
            return;
        }

        push();
        l->update(v, L, R);
        r->update(v, L, R);
        d = Data::merge(l->d, r->d);
    }





};



ll count_swaps(vector<int> S){
    int n = S.size() / 2;
    if(n == 1){
        if(S[0] < 0) return 0;
        return 1;
    }

    vector<int> left(n);
    vector<int> right(n);

    int l = 0;
    int r = 0;
    
    for(int i = 0; i < n*2; i++){
        if(S[i] < 0){
            left[l] = i;
            l++;
        }else{
            right[r] = i;
            r++;
        }
    }

    SeggsTree *lTree = new SeggsTree(left, 0, n);
    SeggsTree *rTree = new SeggsTree(right, 0, n);

    ll swaps = 0;

    // for(int i = 0; i < n; i++){
    //     cout << left[i] << ' ';
    // }
    // cout << '\n';

    // for(int i = 0; i < n; i++){
    //     cout << right[i] << ' ';
    // }
    // cout << '\n';

    for(int i = 0; i < n*2; i++){
        // cout << '\n';
        if(i%2==0){
            //left
            int p = lTree->query(i/2, i/2+1).value;
            swaps += p - i;
            
            int low = 0;
            int high = n+1;
            while(high - low > 1){
                int mid = (high + low) / 2;
                if(rTree->query(mid-1, mid).value > p) high = mid;
                else low = mid;
            }

            // cout << low << '\n';
            if(low > 0) rTree->update(1, i/2, low);
            // for(int i = 0; i < n; i++){
            //     cout << rTree->query(i, i+1).value << ' ';
            // }
            // cout << '\n';
        }else{
            int p = rTree->query(i/2, i/2+1).value;
            swaps += p - i;
            
            int low = 0;
            int high = n+1;
            while(high - low > 1){
                int mid = (high + low) / 2;
                if(lTree->query(mid-1, mid).value > p) high = mid;
                else low = mid;
            }

            // cout << low << '\n';
            if(low > 0) lTree->update(1, i/2, low);
            // for(int i = 0; i < n; i++){
            //     cout << lTree->query(i, i+1).value << ' ';
            // }
            // cout << '\n';
        }

        // cout << i << ": " << swaps << '\n' << '\n';
    }

    return swaps;
}

int main(){

    cout << count_swaps({-2, -2, -2, 2, 2, 2});

    return 0;
}

Compilation message (stderr)

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