Submission #784996

#	Time	Username	Problem	Language	Result	Execution time	Memory
784996		thimote75	Radio Towers (IOI22_towers)	C++17	56 / 100	4051 ms	53620 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

const int MAXK = 20;

using idata = vector<int>;
using igrid = vector<idata>;

idata heights;
int nbTowers;

void init(int N, idata H) {
  nbTowers = N;
  heights  = H;
}

int D0 = -1;
idata jumps;
igrid jumps_2k;
igrid sum_2k;

struct MContainer {
  set<pair<int, int>> m;

  void append (int node, int height) {
    m.insert({ height, node });

    auto it = m.find({ height, node });
    while (it != m.begin()) {
      it --;
      m.erase(*it);
      it = m.find({ height, node });
    }
  }
  int query (int height) { // find the first node greater
    auto it = m.upper_bound({ height, - 1 });
    if (it == m.end()) return -1;

    return (*it).second;
  }
};

int toMiddle (int i) {
  if (i == -1) return -1;
  return 2 * i + 1;
}
int toNormal (int i) {
  if (i == -1) return -1;
  return 2 * i;
}

void init (int D) {
  // node 2i     represents node i as a normal node
  // node 2i + 1 represents node i as a middle node
  jumps.clear();
  jumps.resize(2 * nbTowers, - 1);
  jumps_2k.clear();
  jumps_2k.resize(2 * nbTowers, idata(MAXK, -1));
  sum_2k.clear();
  sum_2k.resize(2 * nbTowers, idata(MAXK, 0));
  D0 = D;

  MContainer container;
  MContainer inverted;

  for (int i = nbTowers - 1; i >= 0; i --) {
    int lnt_mid = container.query( heights[i] + D );
    int lnt_lnt = inverted .query( - heights[i] );
    int mid_mid = container.query( heights[i] );
    int mid_lnt = inverted .query( - heights[i] + D );
    
    jumps[toNormal(i)] = toMiddle(lnt_mid);
    if (lnt_mid == -1 || (lnt_lnt != -1 && lnt_lnt < lnt_mid))
      jumps[toNormal(i)] = toNormal(lnt_lnt);
    jumps[toMiddle(i)] = toNormal(mid_lnt);
    if (mid_lnt == -1 || (mid_mid != -1 && mid_mid < mid_lnt))
      jumps[toMiddle(i)] = toMiddle(mid_mid);

    container.append(i, heights[i]);
    inverted.append(i, -heights[i]);
  }

  for (int i = 0; i < 2 * nbTowers; i ++) {
    jumps_2k[i][0] = jumps[i];

    if (jumps[i] != -1 && (i & 1) == 1 && (jumps[i] & 1) == 0)
      sum_2k[i][0] = 1;
  }

  for (int k = 0; k + 1 < MAXK; k ++) {
    for (int i = 0; i < 2 * nbTowers; i ++) {
      sum_2k[i][k + 1] = sum_2k[i][k];
      if (jumps_2k[i][k] == -1) continue ;

      sum_2k[i][k + 1] += sum_2k[jumps_2k[i][k]][k];
      jumps_2k[i][k + 1] = jumps_2k[jumps_2k[i][k]][k];
    }
  }
}

int find (int node, int jump) {
  for (int i = 0; i < MAXK; i ++) {
    if ((1 << i) & jump) {
      node = jumps_2k[node][i];
      if (node == -1) return -1;
    }
  }
  return node;
}
int jump (int node, int max) {
  int a = 0;
  int b = 2 * nbTowers;
  int s = toNormal(node);
  max   = toMiddle(max);

  while (b - a > 1) {
    int c = (a + b) >> 1;
    int j = find(s, c);

    if (j == -1 || j > max) b = c;
    else a = c;
  }

  if (find(s, a) & 1) a --;

  int jump_count = a;
  int res = 0;
  for (int i = 0; i < MAXK; i ++) {
    if ((1 << i) & jump_count) {
      res += sum_2k[s][i];
      s = jumps_2k[s][i];
    }
  }

  return 1 + res;
}

int max_towers(int L, int R, int D) {
  if (D != D0) {
    init(D);
  }

  return jump(L, R);
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 19 / 19
• Subtask 7: 0 / 23