Submission #101994

#	Time	Username	Problem	Language	Result	Execution time	Memory
101994		naoai	Jousting tournament (IOI12_tournament)	C++14	100 / 100	166 ms	10344 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 5;

int n;

struct Aib {
    int v[nmax + 1];

    int lsb (int x) {
        return x & -x;
    }

    void update (int pos, int val) {
        for (int i = pos + 1; i <= n; i += lsb(i))
            v[i] += val;
    }

    int query (int cnt) {
        int ans = 0;
        ++ cnt;
        for (int i = (1 << 18); i > 0; i >>= 1) {
            if (ans + i <= n && v[ans + i] < cnt) {
                cnt -= v[ans + i];
                ans += i;
            }
        }

        return ans;
    }
} aib;

static set<pair<int, int>> s;
static int st[nmax + 1], dr[nmax + 1];

static vector<pair<int, int>> ord;
static int inchide[nmax + 1];

bool cmp (pair<int, int> a, pair<int, int> b) {
    if (a.first != b.first)
        return a.first < b.first;
    return a.second > b.second;
}

void precalc (int N, int C, int *S, int *E) {
    for (int i = 0; i < N; ++ i) {
        s.insert({i, i});
        aib.update(i, 1);
    }

    for (int i = 0; i < C; ++ i) {
        int start = aib.query(S[i]);
        int stop = -1;
        set<pair<int, int>>::iterator it = s.lower_bound({start, start});

        assert(it -> first == start);

        for (int j = S[i]; j <= E[i]; ++ j) {
            stop = it -> second;
            aib.update(it -> first, -1);

            set<pair<int, int>>::iterator aux = it;
            ++ aux;

            s.erase(it);
            it = aux;
        }

        ord.push_back({start, stop});
        ++ inchide[stop];

        s.insert({start, stop});
        aib.update(start, 1);
    }

    sort(ord.begin(), ord.end(), cmp);
}

static pair<int, int> stv[nmax + 1];

bool check (int pos, pair<int, int> intv) {
    if (pos - 1 >= 0 && intv.first <= st[pos - 1])
        return 0;
    if (pos < n - 1 && dr[pos] + 1 <= intv.second)
        return 0;

    return 1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    for (int i = 0; i < N - 1; ++ i) {
        st[i] = -1;
        if (K[i] > R)
            st[i] = i;
        else if (i - 1 >= 0)
            st[i] = st[i - 1];
    }

    for (int i = N - 2; i >= 0; -- i) {
        dr[i] = N;
        if (K[i] > R)
            dr[i] = i;
        else if (i + 1 < N - 1)
            dr[i] = dr[i + 1];
    }

    // precalc starile de paranteze
    precalc(N, C, S, E);

    int ans = -1, pos = -1;
    int ind = 0;
    int top = 0;
    for (int i = 0; i < N; ++ i) {
        while (ind < ord.size() && ord[ind].first == i)
            stv[++ top] = ord[ind ++];

        // caut binar cat rezista
        int sol = top + 1;
        for (int step = (1 << 18); step > 0; step >>= 1) {
            if (sol - step > 0 && check(i, stv[sol - step])) {
                sol -= step;
            }
        }

        int r = top - sol + 1;
        if (r > ans) {
            ans = r;
            pos = i;
        }

        for (int j = 0; j < inchide[i]; ++ j)
            -- top;
    }

    return pos;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ind < ord.size() && ord[ind].first == i)
                ~~~~^~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51