Submission #501296

#	Time	Username	Problem	Language	Result	Execution time	Memory
501296		doowey	Jousting tournament (IOI12_tournament)	C++14	100 / 100	235 ms	22312 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

vector<int> ord;

const int N = (int)2e5 + 10;

struct Node{
    int cnt;
    int lazy;
};

Node T[N * 4 + 512];
int id[N];

void build(int node, int cl, int cr){
    T[node].cnt = cr - cl + 1;
    if(cl == cr)
        return;
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
}

int n;

void push(int node, int cl, int cr){
    if(T[node].lazy){
        T[node].cnt=0;
        if(cl != cr){
            T[node * 2].lazy = 1;
            T[node * 2 + 1].lazy = 1;
        }
        T[node].lazy = 0;
    }
}

void reset(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lazy = 1;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    reset(node * 2, cl, mid, tl, tr);
    reset(node * 2 + 1, mid + 1, cr, tl, tr);
    T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
}


int get(int node, int cl, int cr, int p){
    if(cl == cr){
        return cl;
    }
    int mid = (cl + cr) / 2;
    push(node * 2, cl, mid);
    push(node * 2 + 1, mid + 1, cr);
    T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
    if(T[node * 2].cnt >= p)
        return get(node * 2, cl, mid, p);
    else
        return get(node * 2 + 1, mid + 1, cr, p - T[node * 2].cnt);
}

const int LOG = 18;
int par[LOG][N];
pii segm[N];

int high[N * 2];

void upd(int iq, int v){
    iq += n;
    high[iq] = v;
    iq /= 2;
    while(iq > 0){
        high[iq] = max(high[iq * 2], high[iq * 2 + 1]);
        iq /= 2;
    }
}

int get_high(int li, int ri){
    li += n;
    ri += n;
    int res = -1;
    while(li <= ri){
        if(li % 2 == 1) res = max(res, high[li ++ ]);
        if(ri % 2 == 0) res = max(res, high[ri -- ]);
        li /= 2;
        ri /= 2;
    }
    return res;
}

int GetBestPosition(int _N, int C, int R, int *K, int *S, int *E) {
    ord.push_back(R);
    n = _N;
    for(int i = 0 ; i < n - 1; i ++ ){
        ord.push_back(K[i]);
    }
    for(int i = 0 ; i < n; i ++ ){
        id[i] = i;
        segm[i] = mp(i, i);
    }
    build(1, 0, n - 1);
    int gl, gr;
    int m = n + C;
    int el, er;
    int tl, tr;
    int nid;
    for(int i = 0 ; i < LOG; i ++ ){
        for(int j = 0 ; j < m ; j ++ ){
            par[i][j] = -1;
        }
    }
    for(int i = 0 ; i < C; i ++ ){
        el = S[i];
        er = E[i];
        el ++ ;
        er ++ ;
        tl=n;
        tr=0;
        for(int j = el; j <= er; j ++ ){
            nid = get(1, 0, n - 1, j);
            tl=min(tl,segm[id[nid]].fi);
            tr=max(tr,segm[id[nid]].se);
            par[0][id[nid]] = n + i;
        }
        reset(1, 0, n - 1, tl + 1, tr);
        segm[n + i] = mp(tl, tr);
        id[tl] = n + i;
    }
    for(int lg = 1; lg < LOG; lg ++ ){
        for(int i = 0 ; i < m ; i ++ ){
            if(par[lg-1][i] != -1){
                par[lg][i]=par[lg-1][par[lg-1][i]];
            }
        }
    }
    int u, v;
    for(int i = 0 ; i < n; i ++ ){
        upd(i, ord[i]);
    }
    int winn = -1;
    int maxi = -1;
    int cur_cnt;
    int node;
    int jump;
    for(int i = 0 ; i < n; i ++ ){
        if(i){
            upd(i - 1, ord[i]);
            upd(i, ord[i - 1]);
            swap(ord[i - 1], ord[i]);
        }
        cur_cnt = 0;
        node = i;
        for(int lg = LOG - 1; lg >= 0 ; lg -- ){
            if(par[lg][node] == -1) continue;
            jump = par[lg][node];
            if(get_high(segm[jump].fi, segm[jump].se) == ord[i]){
                node = jump;
                cur_cnt += (1 << lg);
            }
        }
        if(cur_cnt > maxi){
            winn = i;
            maxi = cur_cnt;
        }
    }
    return winn;

}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:115:9: warning: unused variable 'gl' [-Wunused-variable]
  115 |     int gl, gr;
      |         ^~
tournament.cpp:115:13: warning: unused variable 'gr' [-Wunused-variable]
  115 |     int gl, gr;
      |             ^~
tournament.cpp:149:9: warning: unused variable 'u' [-Wunused-variable]
  149 |     int u, v;
      |         ^
tournament.cpp:149:12: warning: unused variable 'v' [-Wunused-variable]
  149 |     int u, v;
      |            ^

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