Submission #625462

#	Time	Username	Problem	Language	Result	Execution time	Memory
625462		model_code	Radio Towers (IOI22_towers)	C++17	56 / 100	4070 ms	55948 KiB

towers

// time_limit/solution-ayaze-d-equals.cpp
#include "towers.h"

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

const int kLogN = 17;
const int kInf = 2'000'000'000;

struct Fenwick {
  int n;
  vector<vector<int>> tree;
  vector<vector<int>> nums;

  void init(int _n, vector<tuple<int, int, int>> vec) {
    n = _n;
    tree.clear();
    nums.clear();
    tree.resize(n+5);
    nums.resize(n+5);

    for (auto &[row, col, _] : vec) { // normalize
      row++; col++;
    }
    for (auto [row, col, _] : vec) {
      for (int i = row ; i < n+5 ; i += i & -i) {
        nums[i].push_back(col);
      }
    }
    for (int i = 0 ; i < n+5 ; i++) {
      nums[i].push_back(-1);
      sort(nums[i].begin(), nums[i].end());
      nums[i].erase(unique(nums[i].begin(), nums[i].end()), nums[i].end());
      tree[i].resize(nums[i].size());
    }
    for (auto [row, col, val] : vec) {
      update(row, col, val);
    }
  }

  int getIdx(int r, int val) {
    return upper_bound(nums[r].begin(), nums[r].end(), val) - nums[r].begin() - 1;
  }

  void update(int r, int c, int val) {
    for (int i = r ; i < n+5 ; i += i & -i) {
      int idx = getIdx(i, c);
      for (int j = idx ; j < static_cast<int>(tree[i].size()) ; j += j & -j) {
        tree[i][j] += val;
      }
    }
  }

  int query(int l, int r) {
    l++; r++;
    int ret = 0;
    for (int x = l ; x > 0 ; x -= x & -x) {
      int idx = getIdx(x, r);
      for (int j = idx ; j > 0 ; j -= j & -j) {
        ret += tree[x][j];
      }
    }
    return ret;
  }
};

vector<int> D_bounds_left, D_bounds_right;
vector<int> left_lower, right_lower;
int N;

void init(int _N, std::vector<int> H) {
  N = _N;

  vector<pair<int, int>> ordered_H;
  for (int i = 0 ; i < N ; i++) {
    ordered_H.push_back({H[i], i});
  }
  sort(ordered_H.begin(), ordered_H.end());

  left_lower.resize(N, -1);
  right_lower.resize(N, -1);
  set<int> active;
  for (auto [_, i] : ordered_H) {
    {
      auto it = active.lower_bound(i);
      if (it != active.begin()) {
        it--;
        left_lower[i] = *it;
      }
    }
    {
      auto it = active.upper_bound(i);
      if (it != active.end()) {
        right_lower[i] = *it;
      }
    }
    active.insert(i);
  }

  vector<vector<int>> sparse_table(N, vector<int>(kLogN, -1));
  for (int i = 0 ; i < N ; i++) {
    sparse_table[i][0] = H[i];
  }
  for (int j = 1 ; j < kLogN ; j++) {
    for (int i = 0 ; i < N ; i++) {
      if (i + (1 << (j-1)) < N) {
        sparse_table[i][j] = max(sparse_table[i][j-1], sparse_table[i + (1 << (j-1))][j-1]);
      }
    }
  }
  function<int(int, int)> queryMax = [&](int l, int r) -> int {
    int lg = 0;
    while (l + (1 << lg) - 1 <= r) lg++;
    lg--;
    return max(sparse_table[l][lg], sparse_table[r - (1 << lg) + 1][lg]);
  };

  for (int i = 0 ; i < N ; i++) {
    int D_max_left = kInf, D_max_right = kInf;
    
    if (left_lower[i] != -1) {
      D_max_left = -1;
      int mx = queryMax(left_lower[i], i);
      D_max_left = mx - H[i];
    }
    if (right_lower[i] != -1) {
      D_max_right = -1;
      int mx = queryMax(i, right_lower[i]);
      D_max_right = mx - H[i];
    }

    D_bounds_left.push_back(D_max_left);
    D_bounds_right.push_back(D_max_right);
  }
}

Fenwick ft;
int last_D = -1;

void build(int D) {
  vector<tuple<int, int, int>> vec;
  for (int i = 0 ; i < N ; i++) {
    int l, r;

    if (left_lower[i] == -1 || D_bounds_left[i] >= D) l = 0; 
    else l = left_lower[i]+1;
    
    if (right_lower[i] == -1 || D_bounds_right[i] >= D) r = N-1;
    else r = right_lower[i]-1;
    // l <= L <= i <= R <= r
    // (l, i) to (i, r)
    // add(l, i)
    // dec(l, r+1)
    // dec(i+1, i)
    // add(i+1, r+1)
    vec.push_back(make_tuple(l, i, 1));
    vec.push_back(make_tuple(l, r+1, -1));
    vec.push_back(make_tuple(i+1, i, -1));
    vec.push_back(make_tuple(i+1, r+1, 1));
  }

  ft.init(N, vec);
}

int max_towers(int L, int R, int D) {
  if (D != last_D) {
    last_D = D;
    build(D);
  }

  return ft.query(L, R);
}

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