Submission #1111990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111990		manhlinh1501	Jousting tournament (IOI12_tournament)	C++17	0 / 100	22 ms	10436 KiB

tournament

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

template<class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int MAXN = 1e5 + 5;
int a[MAXN];
pair<int, int> b[MAXN];
int par[MAXN];

namespace ST {
    int N;
    int tree[1 << 20];
    int act[1 << 20];

    void build(int id, int l, int r) {
        if(l == r) {
            tree[id] = a[r];
            act[id] = 1;
            return;
        }
        int m = (l + r) / 2;
        build(id * 2, l, m);
        build(id * 2 + 1, m + 1, r);
        tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
        act[id] = act[id * 2] + act[id * 2 + 1];
    }

    void init(int _N) {
        N = _N;
        build(1, 1, N);
    }

    int get_max(int id, int l, int r, int u, int v) {
        if(r < u or l > v) return 0;
        if(u <= l and r <= v) return tree[id];
        int m = (l + r) / 2;
        return max(get_max(id * 2, l, m, u, v), get_max(id * 2 + 1, m + 1, r, u, v));
    }

    int get_max(int l, int r) {
        return get_max(1, 1, N, l, r);
    }

    void update(int id, int l, int r, int u, int v) {
        if(r < u or l > v) return;
        if(u <= l and r <= v) {
            act[id] = 0;
            return;
        }
        int m = (l + r) / 2;
        update(id * 2, l, m, u, v);
        update(id * 2 + 1, m + 1, r, u, v);
        act[id] = act[id * 2] + act[id * 2 + 1];
    }

    void update(int l, int r) {
        return update(1, 1, N, l, r);
    }

    int walk(int x) {
        int id = 1, l = 1, r = N;
        while(l < r) {
            int m = (l + r) / 2;
            if(act[id * 2] >= x) {
                id = id * 2;
                r = m;
            } else {
                x = x - act[id * 2];
                id = id * 2 + 1;
                l = m + 1;
            }
        }
        assert(l == r);
        return r;
    }
}

int GetBestPosition(int N, int M, int K, int A[], int S[], int E[]) {
    for(int i = 0; i < N - 1; i++) a[i + 1] = ++A[i];
    for(int i = 0; i < M; i++) {
        b[i] = {++S[i], ++E[i]};
    }
    K++;
    vector<pair<int, int>> c;
    ST::init(N);
    for(int i = 1; i <= M; i++) {
        auto [l, r] = b[i];

        l = ST::walk(l);
        r = ST::walk(r);

        par[l] = r = par[r];
        ST::update(l + 1, r);

        if(K > ST::get_max(l, r - 1)) {
            c.emplace_back(l, 1);
            c.emplace_back(r, -1);
        }
    }
    sort(c.begin(), c.end(), [&](pair<int, int> a, pair<int, int> b) {
        if(a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });
    int cur = 0;
    pair<int, int> ans = {0, 1};
    for(auto [p, x] : c) {
        cur += x;
        if(maximize(ans.first, cur))
            ans.second = p;
    }
    return ans.second - 1;
}

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