oj.uz

Submission #65311

# Submission time Handle Problem Language Result Execution time Memory
65311 2018-08-07T11:18:55 Z zubec Jousting tournament (IOI12_tournament) C++14
100 / 100
 202 ms 43008 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5240 KB Output is correct
2 Correct 6 ms 5284 KB Output is correct
3 Correct 7 ms 5480 KB Output is correct
4 Correct 8 ms 5480 KB Output is correct
5 Correct 9 ms 5480 KB Output is correct
6 Correct 7 ms 5480 KB Output is correct
7 Correct 8 ms 5480 KB Output is correct
8 Correct 9 ms 5508 KB Output is correct
9 Correct 7 ms 5520 KB Output is correct
10 Correct 10 ms 5568 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5588 KB Output is correct
2 Correct 17 ms 7008 KB Output is correct
3 Correct 9 ms 7008 KB Output is correct
4 Correct 14 ms 7008 KB Output is correct
5 Correct 18 ms 7008 KB Output is correct
6 Correct 14 ms 7008 KB Output is correct
7 Correct 12 ms 7252 KB Output is correct
8 Correct 18 ms 7252 KB Output is correct
9 Correct 12 ms 7252 KB Output is correct
10 Correct 17 ms 7308 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 16836 KB Output is correct
2 Correct 202 ms 35808 KB Output is correct
3 Correct 60 ms 35808 KB Output is correct
4 Correct 155 ms 36296 KB Output is correct
5 Correct 177 ms 37644 KB Output is correct
6 Correct 151 ms 37644 KB Output is correct
7 Correct 163 ms 41508 KB Output is correct
8 Correct 165 ms 43008 KB Output is correct
9 Correct 58 ms 43008 KB Output is correct
10 Correct 65 ms 43008 KB Output is correct