Submission #806558

#	Time	Username	Problem	Language	Result	Execution time	Memory
806558		QwertyPi	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1074 ms	6108 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 11;

struct BIT{
    int bit[MAXN] = {};
    void add(int p, int v){
        ++p; for(int i = p; i < MAXN; i += i & -i) bit[i] += v;
    }
    int qry(int p){
        ++p; int r = 0; for(int i = p; i; i -= i & -i) r += bit[i];
        return r;
    }
    int bs(int v){
        int p = 0, s = 0; for(int j = 19; j >= 0; j--) if(p + (1 << j) < MAXN && s + bit[p + (1 << j)] <= v) s += bit[p + (1 << j)], p += (1 << j);
        return p;
    }
} bit;

struct ST{
    int st[20][MAXN];
    void init(int N, int *K){
        for(int i = 0; i < N; i++) st[0][i] = K[i];
        for(int j = 1; j < 20; j++){
            for(int i = 0; i <= N - (1 << j); i++){
                st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    int qry(int l, int r){
        assert(l <= r);
        int d = __lg(r - l + 1);
        return max(st[d][l], st[d][r - (1 << d) + 1]);
    }
} RMQ;

bool isMax(int i, int R, int l, int r){
    assert(l <= i && i <= r);
    return R > RMQ.qry(l, r - 1);
}

struct update{
    int p, c, t;
};

struct range{
    int l, r, l2, r2, t;

    bool include(int i){
        return l <= i && i <= r;
    }

    bool can(int i, int R){
        return t > 0 && R > RMQ.qry(l2, r2 - 1);
    }
};

range operator+ (const range& a, const range& b){
    if(a.t == 0 || b.t == 0) return a.t == 0 ? b : a;
    return {min(a.l, b.l), max(a.r, b.r), a.l2, a.r2, a.t + b.t};
}

int C;
struct SegTree{
    range t[MAXN << 2];
    void init(int *S, int *E, int v = 0, int l = 0, int r = C - 1){
        if(l == r) t[v] = {S[l], E[l], S[l], E[l], 0};
        else{
            int m = (l + r) / 2;
            init(S, E, v * 2 + 1, l, m);
            init(S, E, v * 2 + 2, m + 1, r);
            t[v] = t[v * 2 + 1] + t[v * 2 + 2];
        }
    }
    void enable(int p, int a, int v = 0, int l = 0, int r = C - 1){
        if(l == r) t[v].t = a;
        else{
            int m = (l + r) / 2;
            if(p <= m) enable(p, a, v * 2 + 1, l, m);
            else enable(p, a, v * 2 + 2, m + 1, r);
            t[v] = t[v * 2 + 1] + t[v * 2 + 2];
        }
    }
    int left(int i, int v = 0, int l = 0, int r = C - 1){
        if(l == r){
            if(t[v].include(i)) return l;
            else return C;
        }else{
            int m = (l + r) / 2;
            if(t[v * 2 + 1].include(i)) return left(i, v * 2 + 1, l, m);
            else return left(i, v * 2 + 2, m + 1, r);
        }
    }
    int right(int i, int R, int v = 0, int l = 0, int r = C - 1){
        if(l == r){
            if(t[v].can(i, R)) return l;
            else return -1;
        }else{
            int m = (l + r) / 2;
            if(t[v * 2 + 2].can(i, R)) return right(i, R, v * 2 + 2, m + 1, r);
            else return right(i, R, v * 2 + 1, l, m);
        }
    }
    int sum(int qr, int v = 0, int l = 0, int r = C - 1){
        if(l == r) return qr >= l ? t[v].t : 0;
        else{
            int m = (l + r) / 2;
            if(qr <= m) return sum(qr, v * 2 + 1, l, m);
            else return t[v * 2 + 1].t + sum(qr, v * 2 + 2, m + 1, r);
        }
    }
} st;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    ::C = C;
    for(int i = 0; i < N; i++) bit.add(i, 1);
    for(int i = 0; i < C; i++){
        int l = S[i] == 0 ? 0 : bit.bs(S[i] - 1) + 1;
        int r = bit.bs(E[i]);
        for(int j = E[i] - 1; j >= S[i]; j--){
            bit.add(bit.bs(j), -1);
        }
        S[i] = l, E[i] = r;
    }
    RMQ.init(N, K);
    st.init(S, E);
    int mx = -1, ans = -1;
    vector<update> U; int uid = 0;
    for(int i = 0; i < C; i++){
        U.push_back({S[i], i, 1});
        U.push_back({E[i] + 1, i, 0});
    }
    sort(U.begin(), U.end(), [](update a, update b){
        return a.p < b.p;
    });
    for(int i = 0; i < N; i++){
        while(uid < C * 2 && U[uid].p <= i) st.enable(U[uid].c, U[uid].t), uid++;
        int r = st.right(i, R);
        int cnt = 0;
        for(int j = 0; j < C; j++){
            cnt += S[j] <= i && i <= E[j] && R > RMQ.qry(S[j], E[j] - 1);
        }
        assert(st.sum(r) == cnt);
        int res = st.sum(r);
        if(res > mx){
            mx = res;
            ans = i;
        }

    }
    return ans;
}

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