oj.uz

Submission #101994

# Submission time Handle Problem Language Result Execution time Memory
101994 2019-03-21T09:41:42 Z naoai Jousting tournament (IOI12_tournament) C++14
100 / 100
 166 ms 10344 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 9 ms 896 KB Output is correct
8 Correct 8 ms 896 KB Output is correct
9 Correct 5 ms 644 KB Output is correct
10 Correct 9 ms 768 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5000 KB Output is correct
2 Correct 109 ms 10056 KB Output is correct
3 Correct 63 ms 7416 KB Output is correct
4 Correct 126 ms 10344 KB Output is correct
5 Correct 126 ms 9592 KB Output is correct
6 Correct 166 ms 9464 KB Output is correct
7 Correct 117 ms 9884 KB Output is correct
8 Correct 113 ms 9848 KB Output is correct
9 Correct 51 ms 7248 KB Output is correct
10 Correct 65 ms 7800 KB Output is correct