Submission #501295

#	Time	Username	Problem	Language	Result	Execution time	Memory
501295		doowey	Jousting tournament (IOI12_tournament)	C++14	17 / 100	1093 ms	8172 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;
        }
    }
    vector<int> vse;
    for(int i = 0 ; i < n; i ++ ){
        vse.push_back(i);
    }
    int si, sj;
    for(int qa = 0 ; qa < C; qa ++ ){
        vector<int> novij;
        si = n;
        sj = -1;
        for(int i = S[qa]; i <= E[qa]; i ++ ){
            par[0][id[vse[i]]] = n + qa;
            si = min(si, segm[id[vse[i]]].fi);
            sj = max(sj, segm[id[vse[i]]].se);
            if(i > S[qa])
                vse[i] = -1;
            else
                id[vse[i]] = n + qa;

        }
        segm[n + qa] = mp(si, sj);
        for(auto x : vse)
            if(x != -1)
                novij.push_back(x);
        vse = novij;
    }
    /*
    for(int i = 0 ; i < C; i ++ ){
        el = S[i];
        er = E[i];
        el ++ ;
        er ++ ;
        tl=tr=-1;
        for(int j = el; j <= er; j ++ ){
            nid = get(1, 0, n - 1, j);
            if(j == el)
                tl = nid;
            if(j == er)
                tr = nid;
            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;
    int chk;
    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;
        while(par[0][node] != -1){
            jump = par[0][node];
            chk = -1;
            for(int j = segm[jump].fi; j <= segm[jump].se; j ++ ){
                chk = max(chk, ord[j]);
            }
            if(chk == ord[i]){
                node = jump;
                cur_cnt ++ ;
            }
            else{
                break;
            }
        }
        if(cur_cnt > maxi){
            maxi = cur_cnt;
            winn = i;
        }
    }
    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:117:9: warning: unused variable 'el' [-Wunused-variable]
  117 |     int el, er;
      |         ^~
tournament.cpp:117:13: warning: unused variable 'er' [-Wunused-variable]
  117 |     int el, er;
      |             ^~
tournament.cpp:118:9: warning: unused variable 'tl' [-Wunused-variable]
  118 |     int tl, tr;
      |         ^~
tournament.cpp:118:13: warning: unused variable 'tr' [-Wunused-variable]
  118 |     int tl, tr;
      |             ^~
tournament.cpp:119:9: warning: unused variable 'nid' [-Wunused-variable]
  119 |     int nid;
      |         ^~~
tournament.cpp:177:9: warning: unused variable 'u' [-Wunused-variable]
  177 |     int u, v;
      |         ^
tournament.cpp:177:12: warning: unused variable 'v' [-Wunused-variable]
  177 |     int u, v;
      |            ^

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