Submission #1245094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245094		guanex	Radio Towers (IOI22_towers)	C++20	0 / 100	21 ms	17308 KiB

towers

#include "towers.h"

#include <vector>

#include<bits/stdc++.h>

using namespace std;

vector<int> h;
pair<int, int> st[100005][20];

void init(int N, std::vector<int> H) {
  int mx = 0;
  for(int i = 0; i < N; ++i){
    st[i][0] = {H[i], i};
    h.push_back(H[i]);
  }
  for(int bit = 1; bit <= 19; ++bit){
    for(int i = 0; i < N; ++i){
      st[i][bit] = max(st[i][bit-1], st[i + (1 << (bit-1))][bit-1]);
    }
  }
}

int solve(int l, int r, int d, int lim){
  if(r < l){
    return 0;
  }
  if(l == r){
    if(h[l] <= lim){
      return 1;
    }else{
      return 0;
    }
  }
  int dist = log2(r - l + 1);
  int mid = st[l][dist].second;
  if(st[r - (1 << dist)][dist].first > st[l][dist].first){
    mid = st[r - (1 << dist)][dist].second;
  }
  return solve(l, mid-1, d, h[mid] - d) + solve(mid+1, r, d, h[mid] - d);
}

int max_towers(int L, int R, int D) {
  return solve(L, R, D, 1000000001);
}

• 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