Submission #879420

#	Time	Username	Problem	Language	Result	Execution time	Memory
879420		NeroZein	Two Antennas (JOI19_antennas)	C++17	100 / 100	509 ms	35692 KiB

antennas

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5; 
const int INF = 1e9; 

int n;
int a[N], aa[N], bb[N], ans[N]; 
int d[N * 2], c[N * 2], lz[N * 2];
vector<pair<int, int>> ev[N], qs[N]; 

void push(int nd, int l, int r) {
  d[nd] = max(d[nd], lz[nd] - c[nd]); 
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    lz[nd + 1] = max(lz[nd + 1], lz[nd]); 
    lz[rs] = max(lz[rs], lz[nd]); 
  }
  lz[nd] = -INF; 
}

void upd(int nd, int l, int r, int s, int e, int v) {
  push(nd, l, r); 
  if (l >= s && r <= e) {
    lz[nd] = max(lz[nd], v); 
    push(nd, l, r); 
    return; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (s <= mid) {
    push(rs, mid + 1, r); 
    upd(nd + 1, l, mid, s, e, v); 
  }
  if (mid < e) {
    push(nd + 1, l, mid);
    upd(rs, mid + 1, r, s, e, v); 
  }
  d[nd] = max(d[nd + 1], d[rs]);  
}

void point_upd(int nd, int l, int r, int p, int v) {
  push(nd, l, r); 
  if (l == r) {
    c[nd] = v; 
    push(nd, l, r); 
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    push(rs, mid + 1, r); 
    point_upd(nd + 1, l, mid, p, v); 
  } else {
    push(nd + 1, l, mid); 
    point_upd(rs, mid + 1, r, p, v); 
  }
  d[nd] = max(d[nd + 1], d[rs]); 
  c[nd] = min(c[nd + 1], c[rs]); 
}

int qry(int nd, int l, int r, int s, int e) {
  push(nd, l, r); 
  if (l >= s && r <= e) {
    return d[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e); 
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e); 
    } else {
      return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
    }
  }
}

void solve() {
  fill(c, c + N * 2, INF);
  fill(d, d + N * 2, -INF);
  fill(lz, lz + N * 2, -INF);
  for (int i = 1; i <= n; ++i) {
    for (auto [j, tp] : ev[i]) {
      if (tp == 1) {
        point_upd(0, 0, n + 1, j, a[j]);
      } else {
        point_upd(0, 0, n + 1, j, INF); 
      }
    }
    if (i - aa[i] > 0) {
      upd(0, 0, n + 1, max(0, i - bb[i]), i - aa[i], a[i]); 
    }
    for (auto [l, j] : qs[i]) {
      ans[j] = max(ans[j], qry(0, 0, n + 1, l, i)); 
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> aa[i] >> bb[i];
    ev[min(n + 1, i + aa[i])].emplace_back(i, 1);
    ev[min(n + 1, i + bb[i] + 1)].emplace_back(i, -1);
  }
  int q;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    int l, r;
    cin >> l >> r; 
    qs[r].emplace_back(l, i); 
  }
  fill(ans + 1, ans + 1 + q, -1); 
  solve();
  for (int i = 1; i <= n; ++i) {
    a[i] *= -1; 
  }
  solve(); 
  for (int i = 1; i <= q; ++i) {
    cout << ans[i] << '\n';
  }
  return 0;
}

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