Submission #1256602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256602		Art	Jousting tournament (IOI12_tournament)	C++20	100 / 100	28 ms	4168 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) : n(_n), bit(_n + 7) {}

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

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

    int lower_bound(int S) {
        int res = n + 1, tmp = 0;
        REV (i, 17, 0) {
            int x = tmp | MASK(i);
            if (x <= n) {
                if (bit[x] >= S) {
                    res = x;
                }
                else {
                    S -= bit[x];
                    tmp = x;
                }
            }
        }
        return res;
    }
    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 *base_rankKnight, int *base_L, int *base_R) {
    vector<int> rankKnight(nPerson + 1); // base_rankKnight chỉ có nPerson(0-based idx) ô(do đây là code hàm), mà ta đang biến về mảng nên cần kích thước tăng lên 1(1-based idx), đó là lí do code trước runtime, do tràn mảng
    vector<int> L(nRound + 1);
    vector<int> R(nRound + 1);
    
    REV (i, nPerson - 2, 0) {
        rankKnight[i + 1] = base_rankKnight[i];
    }
    REV (i, nRound - 1, 0) {
        L[i + 1] = base_L[i];
        R[i + 1] = base_R[i];
    }

    FenwickTree fen(nPerson);
    FOR (i, 1, nPerson) {
        high[i + 1] = high[i] + (rankKnight[i] > rankTarget);
        fen.update(i, +1);
        nxt[i] = i + 1;
    }
    nxt[0] = 1;

    FOR (i, 1, nRound) {
        ++L[i]; ++R[i]; // 1-based idx
        L[i] = fen.lower_bound(L[i]);
        R[i] = fen.upper_bound(R[i]);
//        cout << L[i] << ' ' << R[i], el;
        for (int j = L[i]; (j = nxt[j]) < R[i];) {
            fen.update(j, -1);
        }
        nxt[L[i]] = R[i];
        if (high[L[i]] == high[R[i] - 1]) {
            ++f[L[i]];
            --f[R[i]];
        }
    }
    FOR (i, 1, nPerson) {
        f[i] += f[i - 1];
    }
    return max_element(f + 1, f + nPerson + 1) - f - 1; // 0-based idx
}

// 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) {
// //    FOR (i, 1, nPerson - 1) {
//         cin >> rankKnight[i];
//     }
//     REP (i, nRound) {
// //    FOR (i, 1, nRound) {
//         cin >> L[i] >> R[i];
//     }
//     cout << GetBestPosition(nPerson, nRound, rankTarget, rankKnight, L, R);

//     return 0;
// }

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