Submission #885409

#	Time	Username	Problem	Language	Result	Execution time	Memory
885409		chanhchuong123	Jousting tournament (IOI12_tournament)	C++14	0 / 100	29 ms	14700 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

const int MAX = 100010;
int N, C, R;
int K[MAX];
int S[MAX];
int E[MAX];
int ll[MAX];
int rr[MAX];
int bit[MAX];
int rmq[17][MAX];
pair<int, int> pp[MAX];
long long st[MAX << 2];
long long lz[MAX << 2];

void update(int id, int delta) {
    for (; id <= N; id += id & -id)
        bit[id] += delta;
}

int getPos(int k) {
    int pos = 0;
    for (int j = 31 - __builtin_clz(N); j >= 0; --j) if (pos + (1 << j) <= N) {
        if (bit[pos + (1 << j)] <= k) {
            pos += 1 << j;
            k -= bit[pos];
        }
    }
    return pos;
}

void push(int id) {
    if (lz[id] != 0) {
        st[id << 1] += lz[id]; st[id << 1 | 1] += lz[id];
        lz[id << 1] += lz[id]; lz[id << 1 | 1] += lz[id];
        lz[id] = 0;
    }
}

void update(int id, int l, int r, int u, int v, int d) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        st[id] += d;
        lz[id] += d;
        return;
    }
    int mid = l + r >> 1; push(id);
    update(id << 1, l, mid, u, v, d);
    update(id << 1 | 1, mid + 1, r, u, v, d);
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}

void update(int l, int r, int d) {
    d = d == -2 ? -MAX : d;
    update(1, 1, N, l, r, d);
}

int getMax(int l, int r) {
    int k = 31 - __builtin_clz(r - l + 1);
    return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

int solve(void) {
    for (int i = 1; i <= N; ++i) {
        update(i, +1);
        pp[i] = {i, i};
        rmq[0][i] = K[i];
    }
    for (int j = 1; (1 << j) <= N; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= N; ++i)
            rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + (1 << j - 1)]);
    }
    for (int i = 1; i <= C; ++i) {
        int L = getPos(S[i]); ll[i] = pp[L].fi;
        int R = getPos(E[i]); rr[i] = pp[R].se;
        for (int j = E[i] - S[i]; j >= 1; --j) {
            update(getPos(S[i] + 1), -1);
        }
        pp[L] = {ll[i], rr[i]};
    }

    int curPos = 1, curAns = 0;
    for (int i = 1; i <= C; ++i) {
        int maxValue = getMax(ll[i], rr[i] - 1);
        if (R < maxValue) update(ll[i], rr[i], -2);
        if (R > maxValue) update(ll[i], rr[i], +1);
        int id = 1, l = 1, r = N;
        while (l < r) {
            int mid = l + r >> 1; push(id);
            if (st[id << 1] == st[id]) id <<= 1, r = mid; else id = id << 1 | 1, l = mid + 1;
        }
        if (curAns < st[id]) {
            curAns = st[id];
            curPos = l;
        }
    }
    return curPos;
}

int GetBestPosition(int _N, int _C, int _R, int *_K, int *_S, int *_E) {
    N = _N; C = _C; R = _R;
    for (int i = 1; i < N; ++i) {
        K[i] = _K[i - 1];
    }
    for (int i = 1; i <= C; ++i) {
        S[i] = _S[i - 1];
        E[i] = _E[i - 1];
    }
    return solve() - 1;
}

Compilation message (stderr)

tournament.cpp: In function 'void update(int, int, int, int, int, int)':
tournament.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 1; push(id);
      |               ~~^~~
tournament.cpp: In function 'int solve()':
tournament.cpp:75:67: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   75 |             rmq[j][i] = max(rmq[j - 1][i], rmq[j - 1][i + (1 << j - 1)]);
      |                                                                 ~~^~~
tournament.cpp:93:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int mid = l + r >> 1; push(id);
      |                       ~~^~~

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