oj.uz

Submission #806559

# Submission time Handle Problem Language Result Execution time Memory
806559 2023-08-04T07:54:16 Z QwertyPi Jousting tournament (IOI12_tournament) C++14
100 / 100
 102 ms 17984 KB 
#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 res = st.sum(r);
        if(res > mx){
            mx = res;
            ans = i;
        }

    }
    return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 1236 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 5 ms 1224 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 4 ms 1236 KB Output is correct
8 Correct 5 ms 1236 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 5 ms 1236 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6100 KB Output is correct
2 Correct 102 ms 17920 KB Output is correct
3 Correct 31 ms 8508 KB Output is correct
4 Correct 95 ms 17888 KB Output is correct
5 Correct 93 ms 17584 KB Output is correct
6 Correct 77 ms 13168 KB Output is correct
7 Correct 102 ms 17940 KB Output is correct
8 Correct 96 ms 17984 KB Output is correct
9 Correct 21 ms 7780 KB Output is correct
10 Correct 26 ms 8452 KB Output is correct