Submission #1245112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245112		guanex	Radio Towers (IOI22_towers)	C++20	17 / 100	346 ms	37908 KiB

towers

#include "towers.h"

#include <vector>

#include<bits/stdc++.h>

using namespace std;

vector<int> h;
pair<int, int> st[500005][20];
int stt[500005][20];
vector<pair<int, int>> x;
vector<int> suff;

int solve(int l, int r, int d, int lim){
  if(r < l){
    return -1;
  }
  if(l == r){
    x.push_back({lim - h[l], 1});
    return lim - h[l];
  }
  int dist = log2(r - l + 1);
  int mid = st[l][dist].second;
  int mn = min(stt[l][dist], stt[r - (1 << dist) + 1][dist]);
  if(st[r - (1 << dist) + 1][dist].first > st[l][dist].first){
    mid = st[r - (1 << dist) + 1][dist].second;
  }
  //cout << l << " " << r << " " << mid << endl;
  if(lim == 1000000001){
    x.push_back({1000000001, 1});
  }else
    x.push_back({lim - mn, 1});
  int ans = max(solve(l, mid-1, d, h[mid]), solve(mid+1, r, d, h[mid]));
  x.push_back({ans, -1});
  return max(lim - mn, ans);
}

void init(int N, std::vector<int> H) {
  int mx = 0;
  for(int i = 0; i < N; ++i){
    st[i][0] = {H[i], i};
    stt[i][0] = H[i];
    h.push_back(H[i]);
  }
  for(int bit = 1; bit <= 18; ++bit){
    //cout << bit << endl;s
    for(int i = 0; i < N; ++i){
      st[i][bit] = max(st[i][bit-1], st[i + (1 << (bit-1))][bit-1]);
      stt[i][bit] = min(stt[i][bit-1], stt[i + (1 << (bit-1))][bit-1]);
    }
  }
  
  solve(0, N-1, N, 1000000001);
  sort(x.begin(), x.end());
  for(int i = (int)x.size()-1; i >= 0; --i){
    suff.push_back(x[i].second);
    if((int)suff.size() > 1){
      suff[(int)suff.size()-1] += suff[(int)suff.size()-2];
    }
  }
  reverse(suff.begin(), suff.end());
}


int max_towers(int L, int R, int D) {

  if(D <= x[0].first){
    return suff[0];
  }
  int lo = 0;
  int hi = (int)x.size();
  while(hi - lo > 1){
    int mid = lo + (hi - lo) / 2;
    if(x[mid].first < D){
      lo = mid;
    }else{
      hi = mid;
    }
  }
  return suff[hi];
}

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