Submission #1111744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111744		PagodePaiva	Jousting tournament (IOI12_tournament)	C++17	Compilation error	0 ms	0 KiB

tournament

#include<bits/stdc++.h>

using namespace std;

const long long MAXN = 5010;

struct Segtremax{
    pair <long long, long long> tree[4*MAXN]; long long lazy[4*MAXN];
    pair <long long, long long> join(pair <long long, long long> a, pair <long long, long long> b){
        if(a.first < b.first) return b;
        return a;
    }
    void unlazy(long long node, long long l, long long r){
        if(lazy[node] == -1) return;
        tree[node].first = lazy[node];
        if(l != r){
            lazy[2*node] = max(lazy[2*node], lazy[node]);
            lazy[2*node+1] = max(lazy[2*node+1], lazy[node]);
        }
        lazy[node] = -1;
    }
    void build(long long node, long long l, long long r){
        lazy[node] = -1;
        if(l == r){
            tree[node] = {0, l};
            return;
        }
        long long mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1,mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    void update(long long node, long long l, long long r, long long tl, long long tr, long long val){
        if(l > r) return;
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            lazy[node] = val;
            unlazy(node, tl, tr);
            return;
        }
        long long mid = (tl+tr)/2;
        update(2*node, l, r, tl, mid, val);
        update(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    pair <long long, long long> query(long long node, long long l, long long r, long long tl, long long tr){
        if(l > r) return {-1, 0};
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return {-1, 0};
        if(l <= tl and tr <= r) return tree[node];
        long long mid = (tl+tr)/2;
        return join(query(2*node, l,r,tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

struct Segtresum{
    long long tree[4*MAXN], lazy[4*MAXN];
    long long join(long long a, long long b){
        return a+b;
    }
    void unlazy(long long node, long long l, long long r){
        if(lazy[node] == -1) return;
        tree[node] = (r-l+1)*lazy[node];
        if(l != r){
            lazy[2*node] = lazy[node];
            lazy[2*node+1] = lazy[node];
        }
        lazy[node] = -1;
    }
    void build(long long node, long long l, long long r){
        lazy[node] = -1;
        if(l == r){
            tree[node] = 1;
            return;
        }
        long long mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1,mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    void update(long long node, long long l, long long r, long long tl, long long tr, long long val){
        if(l > r) return;
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            lazy[node] = val;
            unlazy(node, tl, tr);
            return;
        }
        long long mid = (tl+tr)/2;
        update(2*node, l, r, tl, mid, val);
        update(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    long long query(long long node, long long l, long long r, long long tl, long long tr){
        if(l > r) return 0;
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return 0;
        if(l <= tl and tr <= r) return tree[node];
        long long mid = (tl+tr)/2;
        return join(query(2*node, l,r,tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} segsum;


long long GetBestPosition(long long n, long long c, long long r, long long *v, long long *s, long long *e) {
    seg.build(1, 1, n);
    long long res = 0, pos = 0;
    for(long long i = 0;i < n;i++){
        seg.update(1, i+1, i+1,1,n, r);
        for(long long j = 0;j < i;j++){
            seg.update(1, j+1,j+1, 1, n, v[j]);
        }
        for(long long j = i;j < n-1;j++){
            seg.update(1, j+2,j+2,1,n, v[j]);
        }
        segsum.update(1,1,n,1,n,1);
        long long ansat = 0;
        for(long long j = 0;j < c;j++){
            long long lt = s[j]+1;
            long long rt = e[j]+1;
            long long bl = 1, br = n;
            long long ansl = 0;
            while(bl <= br){
                long long mid = (bl+br)/2;
                if(segsum.query(1, 1, mid, 1, n) < lt){
                    ansl = mid;
                    bl = mid+1;
                }
                else{
                    br = mid-1;
                }
            }
            ansl++;
            bl = 1, br = n;
            long long ansr = 0;
            while(bl <= br){
                long long mid = (bl+br)/2;
                if(segsum.query(1, 1, mid, 1, n) > rt){
                    br = mid-1;
                }
                else{
                    ansr = mid;
                    bl = mid+1;
                }
            }
            auto [p, t] = seg.query(1, ansl, ansr, 1, n);
            if(p == r) ansat++;
            segsum.update(1, ansl, t-1, 1, n, 0);
            segsum.update(1, t+1, ansr, 1, n, 0);
        }
        if(ansat > res){
            pos = i;
            res = ansat;
        }
    }
    return pos;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDEPeDQ.o: in function `main':
grader.cpp:(.text.startup+0x118): undefined reference to `GetBestPosition(int, int, int, int*, int*, int*)'
collect2: error: ld returned 1 exit status