Submission #316116

#	Time	Username	Problem	Language	Result	Execution time	Memory
316116		MrDomino	The Big Prize (IOI17_prize)	C++14	0 / 100	16 ms	11264 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

const int N = 200000 + 7;
int n;
int t_pre[4 * N];
int t_suf[4 * N];
vector<int> ret[N];

void upd_pre(int v, int tl, int tr, int i, int cnt) {
  if (i < tl) {
    return;
  }
  if (tr <= i) {
    t_pre[v] = min(t_pre[v], cnt);
  } else {
    int tm = (tl + tr) / 2;
    upd_pre(2 * v, tl, tm, i, cnt);
    upd_pre(2 * v + 1, tm + 1, tr, i, cnt);
  }
}

void upd_suf(int v, int tl, int tr, int i, int cnt) {
  if (tr < i) {
    return;
  }
  if (i <= tl) {
    t_suf[v] = min(t_suf[v], cnt);
  } else {
    int tm = (tl + tr) / 2;
    upd_suf(2 * v, tl, tm, i, cnt);
    upd_suf(2 * v + 1, tm + 1, tr, i, cnt);
  }
}

int get_pre(int v, int tl, int tr, int i) {
  if (tr < tl) {
    return N;
  }
  int sol = t_pre[v];
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    sol = min(sol, get_pre(2 * v, tl, tm - 1, i));
    sol = min(sol, get_pre(2 * v + 1, tm + 1, tr, i));
  }
  return sol;
}

int get_suf(int v, int tl, int tr, int i) {
  if (tr < tl) {
    return N;
  }
  int sol = t_suf[v];
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    sol = min(sol, get_suf(2 * v, tl, tm - 1, i));
    sol = min(sol, get_suf(2 * v + 1, tm + 1, tr, i));
  }
  return sol;
}

void upd_pre(int i, int cnt) {
  upd_pre(1, 0, n - 1, i, cnt);
}

void upd_suf(int i, int cnt) {
  upd_suf(1, 0, n - 1, i, cnt);
}

int cnt_pre(int i) {
  return min(i - 1, get_pre(1, 0, n - 1, i));
}

int cnt_suf(int i) {
  return min(n - 1 - i, get_suf(1, 0, n - 1, i));
}

void upd(int i) {
  if (ret[i].empty()) {
    ret[i] = ask(i);
    upd_pre(i, ret[i][0]);
    upd_suf(i, ret[i][1]);
  }
}

int rep(int l, int r, int q) {
  assert(q >= 0);
  if (l > r || q == 0) {
    return 0;
  }
  int m = (l + r) / 2;
  q--;
  upd(m);
  int x = cnt_pre(m);
  int y = cnt_suf(m);
  if (x == 0 && y == 0) {
    return m;
  }
  if (x == 0) {
    return rep(m + 1, r, q);
  } else {
    return rep(l, m - 1, q);
  }
  /// c0 / c1 = x / y
  /// c0 / (c0 + c1) = x / (x + y)
  /// c0 / q = x / (x + y)
  /// c0 = x * q / (x + y)
  int c0 = (long long) x * q / (x + y);
  int c1 = q - c0;
  int val = rep(l, m - 1, c0);
  if (val) {
    return val;
  } else {
    return rep(m + 1, r, c1);
  }
}

int find_best(int nn) {
  n = nn;
  for (int i = 0; i < 4 * N; i++) {
    t_pre[i] = t_suf[i] = N;
  }
  return rep(0, n - 1, 9999 - 100);
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80