Submission #481835

#	Time	Username	Problem	Language	Result	Execution time	Memory
481835		Haruto810198	Jousting tournament (IOI12_tournament)	C++17	100 / 100	83 ms	15956 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define lsb(x) ((x)&(-(x)))

const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

const int MAX = 100010;

int BIT[MAX];
int n;

pii seg[MAX];
int seg_r[MAX];
vi edge[MAX];

int Max[MAX][20];

void modify(int pos, int val){
    while(pos <= n){
        BIT[pos] += val;
        pos += lsb(pos);
    }
}

int Find(int val){ // find smallest x s.t. pref[x] >= val
    int pos = 0;
    int sum = 0;
    for(int j = 19; j >= 0; j--){
        if(pos + (1<<j) <= n and sum + BIT[pos + (1<<j)] < val){
            sum += BIT[pos + (1<<j)];
            pos += (1<<j);
        }
    }
    return pos + 1;
}

int query_max(int ql, int qr){
    if(ql > qr) return -1;
    int rk = __lg(qr - ql + 1);
    return max(Max[ql][rk], Max[qr - (1<<rk) + 1][rk]);
}

int GetBestPosition(int N, int C, int R, int *K, int *st, int *ed){

    n = N;

    // BIT
    FOR(i, 1, n, 1){
        modify(i, 1);
        seg_r[i] = i;
    }

    // s, e: 0 -> 1

    FOR(i, 0, C-1, 1){
        st[i]++, ed[i]++;
        seg[i].F = Find(st[i]) - 1; // 1 -> 0
        seg[i].S = seg_r[ Find(ed[i]) ] - 1;

        seg_r[ Find(st[i]) ] = seg_r[ Find(ed[i]) ];
        FOR(j, 1, ed[i] - st[i], 1){
            modify(Find(st[i] + 1), -1);
        }
    }

    //cerr<<"segments : "<<endl;
    FOR(i, 0, C-1, 1){
        //cerr<<seg[i].F<<" "<<seg[i].S<<endl;
    }

    // sparse table
    FOR(i, 0, n-2, 1){
        Max[i][0] = K[i];
    }

    FOR(j, 1, 19, 1){
        FOR(i, 0, n-2, 1){
            if(i + (1<<(j-1)) <= n-2) Max[i][j] = max(Max[i][j-1], Max[i + (1<<(j-1))][j-1]);
            else Max[i][j] = Max[i][j-1];
        }
    }

    // win condition
    vector<pii> ev; // pos, val
    FOR(i, 0, C-1, 1){
        // win[l, r]: R at[l, r] and R > arr[l] ... arr[r - 1]
        if(R > query_max(seg[i].F, seg[i].S - 1)){
            ev.eb(seg[i].F, 1);
            ev.eb(seg[i].S + 1, -1);
            //cerr<<"win "<<seg[i].F<<" "<<seg[i].S<<endl;
        }
    }

    sort(ev.begin(), ev.end());

    int res_max = 0, res_id = 0, cur = 0;
    for(pii i : ev){
        cur += i.S;
        if(cur > res_max){
            res_max = cur;
            res_id = i.F;
        }
        //cerr<<i.F<<" "<<i.S<<endl;
    }

    return res_id;
}

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