Submission #807691

#	Time	Username	Problem	Language	Result	Execution time	Memory
807691		dong_liu	Two Antennas (JOI19_antennas)	C++17	100 / 100	510 ms	36920 KiB

antennas

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

#define N 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N)) */
#define Q 200000
#define INF 0x3f3f3f3f

int st[N_ * 2], mx[N_ * 2], lz[N_ * 2];

void put(int i, int x) {
  lz[i] = max(lz[i], x);
  mx[i] = max(mx[i], lz[i] - st[i]);
}

void pus(int i) {
  if (lz[i] != -INF) {
    put(i << 1 | 0, lz[i]);
    put(i << 1 | 1, lz[i]);
    lz[i] = -INF;
  }
}

void pul(int i) {
  int l = i << 1 | 0, r = i << 1 | 1;

  st[i] = min(st[l], st[r]);
  mx[i] = max(mx[l], mx[r]);
}

void update(int u, int l, int r, int ql, int qr, int x) {
  int m;

  if (qr < l || ql > r) assert(0);
  if (ql <= l && qr >= r) {
    put(u, x);
    return;
  }
  pus(u);
  m = (l + r) >> 1;
  if (ql <= m) update(u << 1 | 0, l, m, ql, qr, x);
  if (m < qr) update(u << 1 | 1, m + 1, r, ql, qr, x);
  pul(u);
}

void update_point(int u, int l, int r, int i, int x) {
  int m;

  if (l == r) {
    st[u] = x;
    lz[u] = -INF;
    return;
  }
  pus(u);
  m = (l + r) >> 1;
  if (i <= m)
    update_point(u << 1 | 0, l, m, i, x);
  else
    update_point(u << 1 | 1, m + 1, r, i, x);
  pul(u);
}

int query(int u, int l, int r, int ql, int qr) {
  int m, x;

  if (qr < l || ql > r) assert(0);
  if (ql <= l && qr >= r) return mx[u];
  pus(u);
  m = (l + r) >> 1, x = -1;
  if (ql <= m) x = max(x, query(u << 1 | 0, l, m, ql, qr));
  if (m < qr) x = max(x, query(u << 1 | 1, m + 1, r, ql, qr));
  return x;
}

vector<array<int, 2>> ev[N + 1], qq[N];
int hh[N], aa[N], bb[N], ans[Q], n, n_;

void solve() {
  memset(st, 0x3f, n_ * 2 * sizeof *st);
  memset(mx, -1, n_ * 2 * sizeof *mx);
  memset(lz, -0x3f, n_ * 2 * sizeof *lz);
  for (int i = 0; i < n; i++) {
    for (auto [j, t] : ev[i]) {
      if (t == +1)
        update_point(1, 0, n - 1, j, hh[j]);
      else
        update_point(1, 0, n - 1, j, INF);
    }
    if (i - aa[i] >= 0)
      update(1, 0, n - 1, max(0, i - bb[i]), i - aa[i], hh[i]);
    for (auto [j, h] : qq[i]) {
      int x = query(1, 0, n - 1, j, i);

      ans[h] = max(ans[h], x);
    }
  }
}

int main() {
  int q;

  scanf("%d", &n);
  n_ = 1;
  while (n_ < n) n_ <<= 1;
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d", &hh[i], &aa[i], &bb[i]);
    ev[min(n, i + aa[i])].push_back({i, +1});
    ev[min(n, i + bb[i] + 1)].push_back({i, -1});
  }
  scanf("%d", &q);
  memset(ans, -1, q * sizeof *ans);
  for (int h = 0; h < q; h++) {
    int l, r;

    scanf("%d%d", &l, &r), l--, r--;
    qq[r].push_back({l, h});
  }
  solve();
  for (int i = 0; i < n; i++) hh[i] *= -1;
  solve();
  for (int h = 0; h < q; h++) printf("%d\n", ans[h]);
  return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
antennas.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d%d%d", &hh[i], &aa[i], &bb[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
antennas.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     scanf("%d%d", &l, &r), l--, r--;
      |     ~~~~~^~~~~~~~~~~~~~~~

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