Submission #1036533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036533		juicy	Two Antennas (JOI19_antennas)	C++17	100 / 100	355 ms	32708 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, inf = 1e9 + 7;

int n, q;
int h[N], a[N], b[N], s[4 * N], mn[4 * N], lz[4 * N], res[N];
vector<int> cands, events[N];
vector<array<int, 3>> Queries;

void bld(int id = 1, int l = 1, int r = n) {
  s[id] = -inf, lz[id] = 0, mn[id] = inf;
  if (l == r) { 
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r); 
}

void app(int id, int x) {
  s[id] = max(s[id], x - mn[id]);
  lz[id] = max(lz[id], x);
} 

void psh(int id) {
  if (lz[id]) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
  }
}

void upd(int i) {
  int id = 1, l = 1, r = n;
  while (l ^ r) {
    int md = (l + r) / 2;
    psh(id);
    id *= 2;
    if (i <= md) {
      r = md;
    } else {
      l = md + 1;
      id += 1;
    }
  }
  mn[id] = mn[id] == inf ? h[i] : inf;
  while (id > 1) {
    id /= 2;
    mn[id] = min(mn[id * 2], mn[id * 2 + 1]);
    s[id] = max(s[id * 2], s[id * 2 + 1]);
  }
}

void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    app(id, x);
    return;
  }
  psh(id);
  int md = (l + r) / 2;
  if (u <= md) {
    upd(u, v, x, id * 2, l, md);
  }
  if (md < v) {
    upd(u, v, x, id * 2 + 1, md + 1, r);
  }
  s[id] = max(s[id * 2], s[id * 2 + 1]);
}

int qry(int u, int v, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return s[id];
  }
  psh(id);
  int md = (l + r) / 2;
  if (v <= md) { 
    return qry(u, v, id * 2, l, md);
  }
  if (md < u) {
    return qry(u, v, id * 2 + 1, md + 1, r);
  }
  return max(qry(u, v, id * 2, l, md), qry(u, v, id * 2 + 1, md + 1, r));
}

void solve() {
  bld();
  for (int i = n, j = 0; i > 0; --i) {
    for (int j : events[i]) {
      upd(j);
    }
    int l = i + a[i], r = min(n, i + b[i]);
    if (l <= r) {
      upd(l, r, h[i]);
    }
    while (j < q && Queries[j][0] == i) {
      auto [l, r, id] = Queries[j++];
      res[id] = max(res[id], qry(l, r));
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> h[i] >> a[i] >> b[i];
    int l = max(1, i - b[i]), r = i - a[i];
    if (l <= r) {
      events[r].push_back(i);
      events[l - 1].push_back(i);
    }
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    res[i] = -1;
    Queries.push_back({l, r, i});
  }
  sort(Queries.rbegin(), Queries.rend());
  solve();
  for (int i = 1; i <= n; ++i) {
    h[i] = inf - h[i] + 1;
  }
  solve();
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

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