Submission #1035070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035070		thinknoexit	Jousting tournament (IOI12_tournament)	C++17	0 / 100	21 ms	8692 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
set<int> now;
int n, c, rr;
int k[N], s[N], e[N];
int L[N], R[N];
int fw[N], rmq[18][100100];
vector<int> v[N];
int qrymx(int l, int r) {
    int bit = 31 - __builtin_clz(r - l + 1);
    return max(rmq[bit][l], rmq[bit][r - (1 << bit) + 1]);
}
int deb(int l, int r) {
    int bit = 31 - __builtin_clz(r - l + 1);
    cout << bit << '\n';
    cout << l << ' ' << l + (1 << bit) - 1 << '\n';
    cout << r - (1 << bit) + 1 << ' ' << r << '\n';
    cout << "------------\n";
    return 0;
}
int query(int x) {
    int ans = 0;
    for (;x > 0;x -= x & -x) ans += fw[x];
    return ans;
}
void update(int x, int w) {
    for (;x <= n;x += x & -x) fw[x] += w;
}
int GetBestPosition(int _N, int _C, int _R, int* K, int* S, int* E) {
    n = _N, c = _C, rr = _R + 1;
    for (int i = 0;i < n - 1;i++) {
        k[i + 1] = K[i] + 1;
    }
    for (int i = 0;i < c;i++) {
        s[i + 1] = S[i] + 1;
        e[i + 1] = E[i] + 1;
    }
    for (int i = 1;i <= c;i++) {
        int ql = s[i] + query(s[i]), qr = e[i] + query(e[i]);
        L[i] = ql, R[i] = qr;
        update(L[i], e[i] - s[i]);
        v[L[i]].push_back(i);
        v[R[i] + 1].push_back(-i);
        //cout << L[i] << ' ' << R[i] << '\n';
    }
    // for (int i = 1;i <= 5;i++) {
    //     for (int j = i + 1;j <= 5;j++) {
    //         deb(i, j);
    //     }
    // }
    // RMQ
    for (int i = 1;i < n;i++) rmq[0][i] = k[i];
    for (int i = 0;i < 17;i++) {
        for (int j = 1;j + (2 << i) - 1 < n;j++) rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
    }
    memset(fw, 0, sizeof fw);
    int ans = 0, mx = -1;
    for (int i = 1;i <= n;i++) {
        for (auto& x : v[i]) {
            if (x < 0) now.erase(-x), update(-x, -1);
            else now.insert(x), update(x, 1);
        }
        int l = (*now.begin()) - 1, r = n;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            int x = *now.lower_bound(mid);
            int ql = L[x], qr = R[x];
            // K[ql, ...,i-1], [i, ..., qr-1]
            if (qrymx(ql, qr - 1) < rr) l = mid;
            else r = mid - 1;
        }
        int val = query(l);
        if (val > mx) {
            mx = val;
            ans = i;
        }
    }
    return ans - 1;
}

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