Submission #65311

#	Time	Username	Problem	Language	Result	Execution time	Memory
65311		zubec	Jousting tournament (IOI12_tournament)	C++14	100 / 100	202 ms	43008 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int N = 100100;

vector <int> g[N+N];

pair<int, int> pr[N+N];

int cnt, n, pref[N], id[N], up[N+N][20], deep[N+N];
int t[N*4], ob[N*4];

void push(int v, int l, int r){
    if (ob[v] == 0)
        return;
    int mid = (l+r)>>1;
    t[v+v] = (mid-l+1)*(ob[v]-1);
    t[v+v+1] = (r-mid)*(ob[v]-1);
    ob[v+v] = ob[v+v+1] = ob[v];
    ob[v] = 0;
}

void update(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr)
        return;
    if (tl <= l && r <= tr){
        t[v] = (r-l+1)*x;
        ob[v] = x+1;
        return;
    }
    push(v, l, r);
    int mid = (l+r)>>1;
    update(v+v, l, mid, tl, tr, x);
    update(v+v+1, mid+1, r, tl, tr, x);
    t[v] = t[v+v] + t[v+v+1];
}

int get(int v, int l, int r, int x){
    if (l == r)
        return l;
    int mid = (l+r)>>1;
    push(v, l, r);
    if (t[v+v] <= x)
        return get(v+v+1, mid+1, r, x-t[v+v]); else
        return get(v+v, l, mid, x);
}

void dfs(int v, int p){
    if (p != -1)
        deep[v] = deep[p] + 1;
    up[v][0] = p;
    for (int i = 1; i < 20; i++){
        if (up[v][i-1] != -1)
            up[v][i] = up[up[v][i-1]][i-1];
    }
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        dfs(to, v);
    }
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    update(1, 1, n, 1, n, 1);
    for (int i = 0; i < n; i++){
        pr[i] = {i, i};
        id[i] = i;
    }
    for (int i = 0; i < n-1; i++){
        if (i != 0)
            pref[i] += pref[i-1];
        pref[i] += (K[i] > R);
    }
    cnt = n-1;
    int sz = n;
    //cout << endl;
    for (int i = 0; i < C; i++){
        int l = S[i], r = E[i];
        ++cnt;
        int lpos = get(1, 1, n, l);
        int rpos = get(1, 1, n, r);
        pr[cnt] = {pr[id[lpos-1]].first, pr[id[rpos-1]].second};
        g[cnt].push_back(id[lpos-1]);
        g[cnt].push_back(id[rpos-1]);
        for (int j = l+1; j < r; j++){
            g[cnt].push_back( id[get(1, 1, n, j)-1] );
        }
        id[lpos-1] = cnt;
        update(1, 1, n, lpos+1, rpos, 0);
    }
    for (int i = 0; i <= cnt; i++)
        for (int j = 0; j < 20; j++)
            up[i][j] = -1;
    dfs(cnt, -1);

    int mx = -1;
    int pos = 0;
    for (int i = 0; i < n; i++){
        int cur = 0;
        int v = i;
        for (int j = 19; j >= 0; j--){
            int x = up[v][j];
            if (x == -1)
                continue;
            int l = pr[x].first, r = pr[x].second;
            int kol = 1;
            if (l <= i && i <= r){
                kol = pref[r-1]-pref[l-1];
            }
            if (kol == 0)
                v = x;
        }
        /*for (int j = 0; j < C; j++){
            int l = pr[n+j].first, r = pr[n+j].second;
            int kol = 1;
            if (l <= i && i <= r){
                kol = pref[r-1]-pref[l-1];
                if (kol == 0)
                    ++cur;
            }
        }*/
        cur = deep[i]-deep[v];
        //cout << i << ' ' << cur << endl;
        if (cur > mx){
            mx = cur;
            pos = i;
        }
    }

    return pos;
}

/**

5 3 3
1 0 2 4
1 3
0 1
0 1

*/

Compilation message (stderr)

tournament.cpp: In function 'void dfs(int, int)':
tournament.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:76:9: warning: unused variable 'sz' [-Wunused-variable]
     int sz = n;
         ^~

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