Submission #1256595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256595		Art	Jousting tournament (IOI12_tournament)	C++20	0 / 100	0 ms	320 KiB

tournament

//      - Art -
#include <bits/stdc++.h>

#define el              cout << '\n'
#define MASK(x)         (1 << (x))
#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 1e5 + 7;

using namespace std;

struct FenwickTree {
    int n;
    vector<int> bit;

    FenwickTree(int _n = 0) : n(_n), bit(_n + 7, 0) {}

    void init(int _n) { n = _n; bit.assign(n + 7, 0); }

    void update(int u, int add) {
        if (u <= 0) return;
        for (; u <= n; u += u & -u) bit[u] += add;
    }

    int get(int u) {
        if (u <= 0) return 0;
        int res = 0;
        for (; u > 0; u -= u & -u) res += bit[u];
        return res;
    }

    int lower_bound(int S) {
        if (S <= 1) {
            if (n >= 1) return 1;
            else return n + 1;
        }
        int total = get(n);
        if (S > total) return n + 1;

        int idx = 0;
        int bitmask = 1;
        while ((bitmask << 1) <= n) bitmask <<= 1;
        for (int step = bitmask; step > 0; step >>= 1) {
            int nxt = idx + step;
            if (nxt <= n && bit[nxt] < S) {
                S -= bit[nxt];
                idx = nxt;
            }
        }
        return idx + 1;
    }

    int upper_bound(int S) {
        return lower_bound(S + 1);
    }
};

int high[N], nxt[N], f[N];

int GetBestPosition(int nPerson, int nRound, int rankTarget, int *rankKnight, int *L, int *R) {

    FenwickTree fen(nPerson);
    fen.init(nPerson);

    for (int i = nPerson - 1; i >= 1; --i) {
        rankKnight[i] = rankKnight[i - 1];
    }

    high[0] = 0;
    FOR (i, 1, nPerson) {
        if (i <= nPerson - 1) high[i] = high[i - 1] + (rankKnight[i] > rankTarget ? 1 : 0);
        else high[i] = high[i - 1];
    }

    FOR (i, 1, nPerson) {
        fen.update(i, +1);
        nxt[i] = i + 1;
    }
    nxt[0] = 1;
    FOR(i, 0, nPerson) f[i] = 0;

    FOR (i, 1, nRound) {
        int Si = L[i - 1];
        int Ei = R[i - 1];
        ++Si; ++Ei;
        int Li = fen.lower_bound(Si);
        int Ri = fen.upper_bound(Ei);
        if (Li > nPerson) Li = nPerson + 1;
        if (Ri > nPerson) Ri = nPerson + 1;

        int j = nxt[Li];
        while (j < Ri) {
            fen.update(j, -1);
            int tmp = nxt[j];
            j = tmp;
        }
        nxt[Li] = Ri;

        if (Ri - 1 >= 1 && Li >= 1 && high[Li] == high[Ri - 1]) {
            ++f[Li];
            --f[Ri];
        }
    }

    FOR (i, 1, nPerson) {
        f[i] += f[i - 1];
    }
    int bestPos1 = 1;
    int bestVal = f[1];
    FOR (i, 2, nPerson) {
        if (f[i] > bestVal) {
            bestVal = f[i];
            bestPos1 = i;
        }
    }
    return bestPos1 - 1; 
}

// int rankKnight[N], L[N], R[N];

// int main() {

//     #define name1 "art"
//     if (fopen(name1".inp", "r")) {
//         freopen(name1".inp", "r", stdin);
//         freopen(name1".out", "w", stdout);
//     }

//     #define name "tournament"
//     if (fopen(name".inp", "r")) {
//         freopen(name".inp", "r", stdin);
//         freopen(name".out", "w", stdout);
//     }

//     ios_base::sync_with_stdio(false);
//     cin.tie(0); cout.tie(0);

//     int nPerson, nRound, rankTarget;
//     cin >> nPerson >> nRound >> rankTarget;
//     REP (i, nPerson - 1) {
//         cin >> rankKnight[i];
//     }
//     REP (i, nRound) {
//         cin >> L[i] >> R[i];
//     }
//     cout << GetBestPosition(nPerson, nRound, rankTarget, rankKnight, L, R) << '\n';

//     return 0;
// }

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