Submission #1267329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267329		LucaLucaM	Two Antennas (JOI19_antennas)	C++20	13 / 100	3095 ms	17864 KiB

antennas

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int INF = 1e9;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n;
  std::cin >> n;

  std::vector<int> h(n), lt(n), rt(n);

  for (int i = 0; i < n; i++) {
    std::cin >> h[i] >> lt[i] >> rt[i];
  }

  int q;
  std::cin >> q;

  std::vector<std::pair<int, int>> Q(q);
  std::vector<int> answer(q, -1);
  for (auto &[l, r] : Q) {
    std::cin >> l >> r;
    l--, r--;
  }

  auto solve = [&]() {
    std::vector<int> l(n), r(n), l2(n), r2(n);
    std::vector<std::vector<int>> events(n);
    std::vector<std::vector<int>> queries(n);

    for (int i = 0; i < n; i++) {
      l[i] = lt[i] + i;
      r[i] = rt[i] + i;
      l2[i] = i - rt[i];
      r2[i] = i - lt[i];
      if (r[i] + 1 < n) {
        events[r[i] + 1].push_back(-(i + 1));
      }
      if (l[i] < n) {
        events[std::max(0, l[i])].push_back(+(i + 1));
      }
      l2[i] = std::max(l2[i], 0);
      r2[i] = std::min(r2[i], n - 1);
    }

    for (int i = 0; i < q; i++) {
      queries[Q[i].second].push_back(i);
    }

    std::vector<int> a(n, -INF);
    std::vector<int> b(n, -1);
    
    for (int i = 0; i < n; i++) {
      std::sort(events[i].begin(), events[i].end());
      for (int j : events[i]) {
        int p = std::abs(j) - 1;
        if (j > 0) { // add
          a[p] = h[p];
        } else { // remove
          a[p] = -INF;
        }
      }

      for (int j = l2[i]; j <= r2[i]; j++) {
        b[j] = std::max(b[j], a[j] - h[i]);
      }

      for (int id : queries[i]) {
        auto [l, r] = Q[id];
        int cur = -INF;
        for (int j = l; j <= r; j++) {
          cur = std::max(cur, b[j]);
        }
        answer[id] = std::max(answer[id], cur);
      }
    }
  };

  solve();
  
  std::reverse(h.begin(), h.end());
  std::reverse(lt.begin(), lt.end());
  std::reverse(rt.begin(), rt.end());

  for (auto &[l, r] : Q) {
    l = n - 1 - l;
    r = n - 1 - r;
    std::swap(l, r);
  }

  solve();

  for (int x : answer) {
    std::cout << x << '\n';
  }
  
  return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65