Submission #1035085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035085		thinknoexit	Jousting tournament (IOI12_tournament)	C++17	100 / 100	180 ms	20160 KiB

tournament

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 100100;
set<int> now;
int n, c, rr;
int k[N], s[N], e[N], ed[N];
int L[N], R[N];
int fw[N], rmq[18][N];
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 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;
    }
    ordered_set<int> os;
    for (int i = 1;i <= n;i++) os.insert(i), ed[i] = i;
    for (int i = 1;i <= c;i++) {
        auto x = os.find_by_order(s[i] - 1);
        auto y = os.find_by_order(e[i] - 1);
        int ns = *x, ne = ed[*y];
        ed[ns] = ne;
        vector<int> rem;
        for (;x != y;) rem.push_back(*(++x));
        for (auto& x : rem) os.erase(x);
        L[i] = ns;
        R[i] = ne;
        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 = c;
        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;
        }
        //cout << val << ' ';
    }
    return ans - 1;
}

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