oj.uz

Submission #56352

# Submission time Handle Problem Language Result Execution time Memory
56352 2018-07-11T06:33:35 Z aquablitz11 Jousting tournament (IOI12_tournament) C++14
100 / 100
 325 ms 46240 KB 
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
const int N = 200010;
const int LN = 18;

int n, ptr[N], nxt[N], ft[N];

int get(int x) {
    ++x;
    int i = 0, c = 0;
    for (int j = LN-1; j >= 0; --j) {
        int ni = i+(1<<j);
        if (ni <= n && ni-(c+ft[ni]) < x) {
            i = ni;
            c += ft[ni];
        }
    }
    return i;
}

int skip(int x) {
    if (nxt[x] == x) return x;
    return nxt[x] = skip(nxt[x]);
}

void upd(int i) {
    nxt[i] = i+1;
    for (++i; i <= n; i += i&-i)
        ft[i] += 1;
}

int cnt;
vector<int> G[N*2];
int in[N*2], out[N*2], tick, par[N*2][LN], seg[N*4], dep[N*2];

void dfs(int u, int p)
{
    dep[u] = dep[p]+1;
    in[u] = tick++;
    par[u][0] = p;
    for (int i = 1; i < LN; ++i)
        par[u][i] = par[par[u][i-1]][i-1];
    for (auto v : G[u])
        dfs(v, u);
    out[u] = tick;
}

void updseg(int p, int x)
{
    for (seg[p += cnt] = x; p > 1; p >>= 1)
        seg[p>>1] = max(seg[p], seg[p^1]);
}

int getmax(int l, int r)
{
    int ans = 0;
    for (l += cnt, r += cnt; l < r; l >>= 1, r >>= 1) {
        if (l&1) ans = max(ans, seg[l++]);
        if (r&1) ans = max(ans, seg[--r]);
    }
    return ans;
}

int trylift(int s, int r)
{
    int u = s;
    for (int i = LN-1; i >= 0; --i) {
        int v = par[u][i];
        if (getmax(in[v], out[v]) == r)
            u = v;
    }
    return dep[s]-dep[u];
}

int GetBestPosition(int n, int c, int r, int *K, int *S, int *E)
{
    ::n = n;
    cnt = n;
    for (int i = 0; i < n; ++i)
        ptr[i] = i, nxt[i] = i;
    nxt[n] = n;
    for (int i = 0; i < c; ++i) {
        int s = get(S[i]);
        int e = get(E[i]);
        for (int j = s; j <= e; j = skip(j)) {
            G[cnt].push_back(ptr[j]);
            if (j != s) {
                ptr[j] = -1;
                upd(j);
            } else {
                ++j;
            }
        }
        ptr[s] = cnt++;
    }
    dfs(cnt-1, cnt-1);

    updseg(in[0], r);
    for (int i = 0; i < n-1; ++i)
        updseg(in[i+1], K[i]);
    pii ans(trylift(0, r), 0);
    for (int i = 1; i < n; ++i) {
        updseg(in[i], r);
        updseg(in[i-1], K[i-1]);
        ans = max(ans, pii(trylift(i, r), -i));
    }

    return -ans.second;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9720 KB Output is correct
2 Correct 12 ms 9964 KB Output is correct
3 Correct 12 ms 10016 KB Output is correct
4 Correct 12 ms 10016 KB Output is correct
5 Correct 13 ms 10016 KB Output is correct
6 Correct 14 ms 10060 KB Output is correct
7 Correct 14 ms 10088 KB Output is correct
8 Correct 13 ms 10092 KB Output is correct
9 Correct 16 ms 10136 KB Output is correct
10 Correct 12 ms 10196 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10292 KB Output is correct
2 Correct 24 ms 11620 KB Output is correct
3 Correct 17 ms 11620 KB Output is correct
4 Correct 22 ms 11620 KB Output is correct
5 Correct 19 ms 11620 KB Output is correct
6 Correct 20 ms 11620 KB Output is correct
7 Correct 21 ms 11920 KB Output is correct
8 Correct 24 ms 11920 KB Output is correct
9 Correct 13 ms 11920 KB Output is correct
10 Correct 26 ms 11920 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 20128 KB Output is correct
2 Correct 300 ms 39600 KB Output is correct
3 Correct 144 ms 39600 KB Output is correct
4 Correct 278 ms 39600 KB Output is correct
5 Correct 321 ms 40972 KB Output is correct
6 Correct 206 ms 40972 KB Output is correct
7 Correct 325 ms 44764 KB Output is correct
8 Correct 318 ms 46240 KB Output is correct
9 Correct 158 ms 46240 KB Output is correct
10 Correct 137 ms 46240 KB Output is correct