Submission #806479

#	Time	Username	Problem	Language	Result	Execution time	Memory
806479		QwertyPi	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1062 ms	3916 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);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    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);
    int mx = -1, ans = -1;
    for(int i = 0; i < N; i++){
        /*
        int op, ed, l, r;
    
        l = 0, r = C;
        while(l != r){
            int mid = (l + r) / 2;
            bool ok = S[mid] <= i && i <= E[mid];
            if(ok){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        op = l;

        l = op, r = C;
        while(l != r){
            int mid = (l + r + 1) / 2;
            bool ok = isMax(i, R, S[mid - 1], E[mid - 1]);
            if(ok){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        ed = l;

        int res = ed - op;
        if(res > mx){
            mx = res;
            ans = i;
        }
        */

        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);
        }

        if(cnt > mx){
            mx = cnt;
            ans = i;
        }
    }
    return ans;
}

Compilation message (stderr)

tournament.cpp: In member function 'void ST::init(int, int*)':
tournament.cpp:28:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |                 st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
      |                                                                  ~~^~~

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