oj.uz

Submission #134670

# Submission time Handle Problem Language Result Execution time Memory
134670 2019-07-23T07:12:17 Z PeppaPig Jousting tournament (IOI12_tournament) C++14
100 / 100
 128 ms 23060 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1<<17;

struct node {
    int mx, pos;
    vector<int> child;
} g[N<<1];

int n, R;
int idx[N], t[N], tmx[N<<1];

void update(int x, int k) { if(x <= n) t[x] += k, update(x + (x & -x), k); }

int query(int x) { return t[x] + (x ? query(x - (x & -x)) : 0); }

int get(int x) {
    int l = 1, r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(query(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return r;
}

int query(int l, int r) {
    int ret = 0;
    for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) ret = max(ret, tmx[l++]);
        if(r & 1) ret = max(ret, tmx[--r]);
    }
    return ret;
}

int ans, ans_pos;

pii dfs(int u) {
    if(g[u].child.empty()) return pii(g[u].pos, g[u].pos);
    int l = n + 1, r = 0;
    g[u].pos = 1e9;
    for(int v : g[u].child) {
        pii now = dfs(v);
        l = min(l, now.x), r = max(r, now.y);
        if(g[v].mx > g[u].mx) g[u].mx = g[v].mx, g[u].pos = 1e9;
        if(g[v].mx == g[u].mx && g[v].pos < g[u].pos) g[u].pos = g[v].pos;
    }
    ++g[u].mx;
    if(query(l, r - 1) < R) {
        if(g[u].mx > ans) ans = g[u].mx, ans_pos = 1e9;
        if(g[u].mx == ans && g[u].pos < ans_pos) ans_pos = g[u].pos;
    }
    return pii(l, r);
}

int GetBestPosition(int _n, int C, int R, int *K, int *S, int *E) {
    n = _n, ::R = R;
    for(int i = 1; i <= n; i++) {
        update(i, 1);
        idx[i] = i, g[i].pos = i;
        tmx[i + N] = K[i-1];
    }
    for(int i = N-1; i; i--) tmx[i] = max(tmx[i<<1], tmx[i<<1|1]);
    for(int i = 1; i <= C; i++) {
        int s = S[i-1] + 1, e = E[i-1] + 1;
        vector<int> vec;
        for(int j = s; j <= e; j++) vec.emplace_back(get(j));
        for(int v : vec) {
            g[i + n].child.emplace_back(idx[v]);
            if(v != vec[0]) update(v, -1);
        }
        idx[vec[0]] = i + n;
    }
    dfs(n + C);
    return ans_pos - (ans_pos ? 1 : 0);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9208 KB Output is correct
2 Correct 10 ms 9080 KB Output is correct
3 Correct 10 ms 9080 KB Output is correct
4 Correct 10 ms 9080 KB Output is correct
5 Correct 10 ms 9080 KB Output is correct
6 Correct 11 ms 9080 KB Output is correct
7 Correct 10 ms 9080 KB Output is correct
8 Correct 10 ms 9084 KB Output is correct
9 Correct 10 ms 9080 KB Output is correct
10 Correct 10 ms 9084 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9208 KB Output is correct
2 Correct 15 ms 9848 KB Output is correct
3 Correct 12 ms 9208 KB Output is correct
4 Correct 15 ms 9464 KB Output is correct
5 Correct 15 ms 9592 KB Output is correct
6 Correct 15 ms 9308 KB Output is correct
7 Correct 18 ms 9596 KB Output is correct
8 Correct 15 ms 9464 KB Output is correct
9 Correct 12 ms 9208 KB Output is correct
10 Correct 16 ms 9464 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11896 KB Output is correct
2 Correct 128 ms 23060 KB Output is correct
3 Correct 59 ms 12660 KB Output is correct
4 Correct 123 ms 18808 KB Output is correct
5 Correct 124 ms 20140 KB Output is correct
6 Correct 126 ms 14428 KB Output is correct
7 Correct 124 ms 20216 KB Output is correct
8 Correct 125 ms 20216 KB Output is correct
9 Correct 52 ms 12272 KB Output is correct
10 Correct 70 ms 12024 KB Output is correct