Submission #635094

#	Time	Username	Problem	Language	Result	Execution time	Memory
635094		ruhanhabib39	Radio Towers (IOI22_towers)	C++17	23 / 100	4091 ms	23328 KiB

towers

#include "towers.h"

#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>

namespace ruhan {
   using namespace std;

   int N;
   vector<int> H;
   vector<int> max_rmq[20];
   vector<int> min_rmq[20];

   int good_pos = -1;

   vector<int> lg;

   int my_max (int x, int y) {
      return H[x] > H[y] ? x : y;
   }

   int my_min (int x, int y) {
      return H[x] < H[y] ? x : y;
   }

   template<class F>
   void rmq_init (vector<int> *rmq, F func) {
      rmq[0].resize(N);
      iota(rmq[0].begin(), rmq[0].end(), 0);
      for (int k = 0; k < 19; k++) {
         rmq[k+1].resize(N);
         for (int i = 0; i < N; i++) {
            if (i + (1 << k) < N) rmq[k+1][i] = func(rmq[k][i], rmq[k][i+(1<<k)]);
            else rmq[k+1][i] = rmq[k][i];
         }
      }
   }

   template<class F>
   int rmq_get (vector<int> *rmq, F func, int l, int r) {
      int k = lg[r - l + 1];

      return func(rmq[k][l], rmq[k][r - (1 << k) + 1]);
   }

   void init (int N_, vector<int> H_) {
      N = N_; H = H_;

      for (int i = 0; i < N; i++) {
         if ((i == 0 || H[i-1] < H[i]) && (i == N - 1 || H[i+1] > H[i])) {
            if (good_pos == -1) good_pos = i;
            else good_pos = -2;
         }
      }

      rmq_init(max_rmq, my_max);
      rmq_init(min_rmq, my_min);
      
      lg.resize(N + 1);
      lg[1] = 0;
      for (int x = 2; x <= N; x++) {
         lg[x] = lg[x/2] + 1;
      }

      //cerr << "init done\n";
   }

   int calc (int L, int R, int D, int mx) {
      if (good_pos >= 0) {
         if (good_pos <= L && good_pos >= R) return 1;

         int x = rmq_get(min_rmq, my_min, L, good_pos - 1);
         int y = rmq_get(min_rmq, my_min, good_pos + 1, R);

         if (H[x] + D <= H[good_pos] && H[y] + D <= H[good_pos]) return 2;
         else return 1;
      }

      if (L > R) return 0;
      if (L == R) return H[L] <= mx;

      //cerr << L << " " << R << " " << D << " " << mx << ", ";

      int xi = rmq_get(min_rmq, my_min, L, R);
      int yi = rmq_get(max_rmq, my_max, L, R);

      //cerr << "xi = " << xi << ", yi = " << yi << "\n";

      if (H[xi] > mx) return 0;

      return max(1, calc(L, yi - 1, D, H[yi] - D) + calc(yi + 1, R, D, H[yi] - D));
   }
};

void init(int N, std::vector<int> H) {
   ruhan::init(N, H);
}

int max_towers(int L, int R, int D) {
   return ruhan::calc(L, R, D, int(2e9));
}

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