oj.uz

Submission #784993

# Submission time Handle Problem Language Result Execution time Memory
784993 2023-07-16T21:18:41 Z thimote75 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 3428 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4024 ms 3428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 1824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4024 ms 3428 KB Time limit exceeded
2 Halted 0 ms 0 KB -