Submission #625453

#	Time	Username	Problem	Language	Result	Execution time	Memory
625453		model_code	Radio Towers (IOI22_towers)	C++17	14 / 100	1198 ms	1872 KiB

towers

// incorrect/solution-ayaze-d-one.cpp
#include "towers.h"

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

int N;
vector<int> H;
vector<int> bottoms;

void init(int _N, std::vector<int> _H) {
  N = _N;
  H = _H;
  for (int i = 1 ; i+1 < N ; i++) {
    if (H[i] < H[i+1] && H[i] < H[i-1]) {
      bottoms.push_back(i);
    }
  }
}

int max_towers(int L, int R, int) {
  if (R-L+1 <= 2) return 1;
  
  int bottom_count = upper_bound(bottoms.begin(), bottoms.end(), R-1) - 
                     lower_bound(bottoms.begin(), bottoms.end(), L+1);
  
  if (bottom_count == 0) {
    if (H[L] < H[L+1] && H[R] < H[R-1]) return 2;
    return 1;
  }

  int ret = bottom_count;

  int l_idx = lower_bound(bottoms.begin(), bottoms.end(), L+1) - bottoms.begin();
  int l = bottoms[l_idx];
  if (l > L+1 && H[L] < H[L+1]) ret++;

  int r_idx = upper_bound(bottoms.begin(), bottoms.end(), R-1) - bottoms.begin() - 1;
  int r = bottoms[r_idx];
  if (r < R-1 && H[R] < H[R-1]) ret++;

  return ret;
}

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