oj.uz

Submission #382721

# Submission time Handle Problem Language Result Execution time Memory
382721 2021-03-28T06:09:20 Z ParsaAlizadeh Jousting tournament (IOI12_tournament) C++17
100 / 100
 91 ms 21356 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'
#define lc              (id << 1)
#define rc              (lc | 1)

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 2e5 + 10;

int seg[N << 1], A[N], labl[N], sz[N], H[N], pos[N], ans[2];
vector<int> adj[N];

void Build(int id, int l, int r) {
    if (r - l == 1) {
        seg[id] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    Build(lc, l, mid); Build(rc, mid, r);
    seg[id] = seg[lc] + seg[rc];
}

int Modify(int id, int l, int r, int ind, int val) {
    if (r - l == 1) {
        seg[id] = val;
        return l;
    }
    int mid = (l + r) >> 1, res;
    if (seg[lc] <= ind)
        res = Modify(rc, mid, r, ind - seg[lc], val);
    else
        res = Modify(lc, l, mid, ind, val);
    seg[id] = seg[lc] + seg[rc];
    return res;
}

int okey(int l, int r) {
    return (A[r] - A[l]) == 0;
}

void DFS(int u, int ind) {
    sz[u] = adj[u].empty();
    for (int v : adj[u]) {
        DFS(v, ind + sz[u]);
        sz[u] += sz[v];
        H[u] = max(H[u], H[v] + 1);
    }
    if (H[u] == 0) {
        pos[u] = ind;
        return;
    }
    if (!okey(ind, ind + sz[u] - 1))
        return;
    for (int v : adj[u]) if (H[v] + 1 == H[u]) {
        pos[u] = pos[v];
        break;
    }
    if (H[u] > ans[0] || (H[u] == ans[0] && pos[u] < ans[1]))
        ans[0] = H[u], ans[1] = pos[u];
}

int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
    Build(1, 0, n);
    iota(labl, labl + n, 0);
    int timer = n;
    for (int i = 0; i < C; i++) {
        int l = Modify(1, 0, n, S[i], 1);
        adj[timer].push_back(labl[l]);
        for (int j = 0; j < E[i] - S[i]; j++) {
            int r = Modify(1, 0, n, S[i] + 1, 0);
            adj[timer].push_back(labl[r]);
        }
        labl[l] = timer++;
    }
    int root = timer - 1; //labl[Modify(1, 0, n, 0, 1)];
    for (int i = 1; i < n; i++) {
        A[i] = A[i - 1] + (K[i - 1] > R);
    }
    DFS(root, 0);
    return ans[1];
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5100 KB Output is correct
7 Correct 5 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 8 ms 5868 KB Output is correct
3 Correct 6 ms 5356 KB Output is correct
4 Correct 7 ms 5612 KB Output is correct
5 Correct 7 ms 5612 KB Output is correct
6 Correct 7 ms 5356 KB Output is correct
7 Correct 8 ms 5740 KB Output is correct
8 Correct 8 ms 5612 KB Output is correct
9 Correct 6 ms 5228 KB Output is correct
10 Correct 9 ms 5612 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8172 KB Output is correct
2 Correct 89 ms 21356 KB Output is correct
3 Correct 53 ms 9448 KB Output is correct
4 Correct 91 ms 17132 KB Output is correct
5 Correct 85 ms 18412 KB Output is correct
6 Correct 86 ms 12524 KB Output is correct
7 Correct 87 ms 18540 KB Output is correct
8 Correct 86 ms 18540 KB Output is correct
9 Correct 38 ms 9060 KB Output is correct
10 Correct 43 ms 9456 KB Output is correct