제출 #784993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784993		thimote75	송신탑 (IOI22_towers)	C++17	0 / 100	4046 ms	3428 KiB

towers

#include "towers.h"

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

using idata = vector<int>;

idata heights;
int nbTowers;

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

int D0 = -1;
idata jumps;

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.resize(2 * nbTowers, - 1);
  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]);
  }
}

int jump ( int node, int max ) {
  node = toNormal(node);
  max  = toMiddle(max);
  int res = 1;
  while (node <= max && node != -1) {
    if (jumps[node] != -1 && (node & 1) == 1 && (jumps[node] & 1) == 0)
      res ++;
    node = jumps[node];
  }

  return 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: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23