Submission #1196316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196316		abczz	Two Antennas (JOI19_antennas)	C++20	100 / 100	433 ms	58332 KiB

antennas

#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

vector <array<ll, 2>> V[200001], Q[200001];
ll n, q, a, b, f, H[200000], A[200000], B[200000], F[200000];

struct SegTree{
  ll mx[800004], mn[800004], lazymx[800004], lazymn[800004], st[800004];
  void init() {
    for (int i=0; i<800004; ++i) {
      mx[i] = st[i] = lazymx[i] = -1e18;
      mn[i] = lazymn[i] = 1e18;
    }
  }
  void solve(ll id) {
    st[id] = max(st[id], max(mx[id]-lazymn[id], lazymx[id]-mn[id]));
  }
  void push(ll id) {
    lazymx[id*2] = max(lazymx[id*2], lazymx[id]);
    lazymx[id*2+1] = max(lazymx[id*2+1], lazymx[id]);
    lazymn[id*2] = min(lazymn[id*2], lazymn[id]);
    lazymn[id*2+1] = min(lazymn[id*2+1], lazymn[id]);
    st[id*2] = max(st[id*2], max(mx[id*2]-lazymn[id], lazymx[id]-mn[id*2]));
    st[id*2+1] = max(st[id*2+1], max(mx[id*2+1]-lazymn[id], lazymx[id]-mn[id*2+1]));
    lazymx[id] = -1e18, lazymn[id] = 1e18;
  }
  void pt_update(ll id, ll l, ll r, ll q, ll w) {
    if (l == r) {
      if (w == 1e18) mx[id] = -1e18, mn[id] = 1e18;
      else mx[id] = mn[id] = w;
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) pt_update(id*2, l, mid, q, w);
    else pt_update(id*2+1, mid+1, r, q, w);
    mx[id] = max(mx[id*2], mx[id*2+1]);
    mn[id] = min(mn[id*2], mn[id*2+1]);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  void range_update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      lazymx[id] = max(lazymx[id], w);
      lazymn[id] = min(lazymn[id], w);
      st[id] = max(st[id], max(mx[id]-w, w-mn[id]));
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    range_update(id*2, l, mid, ql, qr, w);
    range_update(id*2+1, mid+1, r, ql, qr, w);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return (ll)-1e18;
    else if (ql <= l && r <= qr) return st[id];
    push(id);
    ll mid = (l+r)/2;
    return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
}ST;
int main() {
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> H[i] >> A[i] >> B[i];
    if (i+A[i] < n) V[i+A[i]].push_back({1, i});
    if (i+B[i]+1 < n) V[i+B[i]+1].push_back({-1, i});
  }
  ST.init();
  cin >> q;
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    --a, --b;
    Q[b].push_back({i, a});
  }
  for (int i=0; i<n; ++i) {
    for (auto [x, y] : V[i]) {
      if (x == 1) ST.pt_update(1, 0, n-1, y, H[y]);
      else if (x == -1) ST.pt_update(1, 0, n-1, y, 1e18);
    }
    if (i != n && i-A[i] >= 0) {
      ST.range_update(1, 0, n-1, max(i-B[i], 0LL), i-A[i], H[i]);
    }
    for (auto [x, y] : Q[i]) {
      F[x] = max(-1LL, ST.query(1, 0, n-1, y, i));
    }
  }
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
  cout << '\n';
}

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