oj.uz

Submission #593480

# Submission time Handle Problem Language Result Execution time Memory
593480 2022-07-11T08:55:48 Z Mamedov Jousting tournament (IOI12_tournament) C++17
100 / 100
 70 ms 26032 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct segTree {
  int N;
  vector<int>tree;
  segTree(int n) {
    N = n;
    tree.assign(4 * N, 0);
  }
  void add(int node, int l, int r, int pos) {
    tree[node]++;
    if (l < r) {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        add(node << 1, l, mid, pos);
      } else {
        add((node << 1) | 1, mid + 1, r, pos);
      }
    }
  }
  int getKth(int node, int l, int r, int k) {
    if (l == r) {
      return l;
    } else {
      int mid = (l + r) >> 1;
      if (mid - l + 1 - tree[node << 1] >= k) {
        return getKth(node << 1, l, mid, k);
      } else {
        return getKth((node << 1) | 1, mid + 1, r, k - (mid - l + 1 - tree[node << 1]));
      }
    }
  }
};

void dfs(int node, vi &psum, vvi &g, vi &l, vi &r, vpii &best) {
  for (int to : g[node]) {
    dfs(to, psum, g, l, r, best);
    l[node] = min(l[node], l[to]);
    r[node] = max(r[node], r[to]);
    if (best[to].f > best[node].f) {
      best[node] = best[to];
    }
  }
  if (size(g[node]) == 0) { /// leaf node
    l[node] = r[node] = node;
    best[node] = mpr(0, node);
  } else if (psum[r[node] - 1] - (l[node] > 0 ? psum[l[node] - 1] : 0) == 0) { /// late knight has highest rank, +1 win
    best[node].f++;
  }
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  vvi g(2 * N);
  int nextNode = N - 1;
  vector<int>root(N);
  for (int i = 0; i < N; ++i) {
    root[i] = i;
  }
  segTree tree(N);
  for (int i = 0; i < C; ++i) {
    int node = tree.getKth(1, 0, N - 1, S[i] + 1);
    g[++nextNode].eb(root[node]);
    root[node] = nextNode;
    for (int j = S[i] + 2; j <= E[i] + 1; ++j) {
      node = tree.getKth(1, 0, N - 1, S[i] + 2);
      tree.add(1, 0, N - 1, node);
      g[nextNode].eb(root[node]);
    }
  }
  vector<int>psum(N - 1, 0);
  for (int i = 0; i < N - 1; ++i) {
    if (K[i] > R) {
      psum[i] = 1;
    }
  }
  for (int i = 1; i < N - 1; ++i) {
    psum[i] += psum[i - 1];
  }
  vector<int>l(2 * N, oo), r(2 * N, 0);
  vpii best(2 * N, mpr(-1, -1));
  dfs(nextNode, psum, g, l, r, best);
  return best[nextNode].s;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 1340 KB Output is correct
8 Correct 3 ms 1208 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 4 ms 980 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7444 KB Output is correct
2 Correct 63 ms 26032 KB Output is correct
3 Correct 29 ms 12236 KB Output is correct
4 Correct 60 ms 20004 KB Output is correct
5 Correct 66 ms 21748 KB Output is correct
6 Correct 61 ms 14620 KB Output is correct
7 Correct 70 ms 22136 KB Output is correct
8 Correct 61 ms 22132 KB Output is correct
9 Correct 26 ms 11912 KB Output is correct
10 Correct 31 ms 12136 KB Output is correct