Submission #1269294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269294		happydavid@aoa	Bubble Sort 2 (JOI18_bubblesort2)	C++20	Compilation error	0 ms	0 KiB

bubblesort2

#include <bits/stdc++.h>
#define inf 1000000001
using namespace std;

struct Seg{
    int n;
    vector<int> Tree, A;

    void init(int N, vector<int> a){
        n = N;
        Tree.assign(4*n, inf);
        for(int i = 0; i < N; i++){
            A.push_back(a[i]);
        }
        build(1, 0, n-1);
    }

    void build(int node, int l, int r){
        if(l == r){
            Tree[node] = A[l];
        } else {
            int mid = (l+r) / 2;
            build(2*node, l, mid);
            build(2*node+1, mid+1, r);
            Tree[node] = min(Tree[2*node], Tree[2*node+1]);
        }
    }

    int min_query(int node, int l, int r, int ql, int qr){
        if(qr < l || ql > r ) return inf;
        if(ql <= l && r <= qr){
            return Tree[node];
        }
        int mid = (l+r)/2;
        return min(min_query(2*node, l, mid, ql, qr), min_query(2*node+1, mid+1, r, ql, qr));
    }

    void update(int node, int l, int r, int i, int val){
        if(l == r) Tree[node] = val, A[i] = val;
        else {
            int mid = (l+r) / 2;
            if(i <= mid){
                update(2*node, l, mid, i, val);
            } else {
                update(2*node+1, mid+1, r, i, val);
            }
            Tree[node] = min(Tree[2*node], Tree[2*node+1]);
        }
    }
};

vector<int> count_scans(vector<int> A, vector<int> X, vector<int> V){
    int n = A.size();
    int m = X.size();
    vector<int> answers;
    Seg seg;
    seg.init(n, A);
    for(int q = 0; q < m; q++){
        seg.update(1, 0, n-1, X[q], V[q]);
        int ans = 0;
        for(int i = 0; i < n-1; i++){
            int current_number = seg.A[i];
            int mi = seg.min_query(1, 0, n-1, i+1, n-1);
            if(mi < current_number) ans++;
        }
        answers.push_back(ans);
    }
    return answers;
}
/*
int main(){
    vector<int> A = {1, 2, 3, 4};
    vector<int> X = {0, 2};
    vector<int> V = {3, 1};
    vector<int> result = count_scans(A, X, V);
    for(const int& x : result){
        cout << x << ' ';
    } cout << endl;

    
    return 0;
}
*/

Compilation message (stderr)

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