Submission #718069

#	Time	Username	Problem	Language	Result	Execution time	Memory
718069		Johann	Two Antennas (JOI19_antennas)	C++14	100 / 100	817 ms	35380 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 1;

struct sdata {
  int minhl = inf, maxhl = -inf, maxcost = -1;
};

struct operation {
  int minhr = inf, maxhr = -inf;
};

sdata combine(sdata dl, sdata dr) {
  return { min(dl.minhl, dr.minhl), max(dl.maxhl, dr.maxhl), max(dl.maxcost, dr.maxcost) };
}

sdata calculate(operation o, sdata d) {
  return { d.minhl, d.maxhl, max(d.maxcost, max(o.maxhr - d.minhl, d.maxhl - o.minhr)) };
}

operation merge(operation ot, operation ob) {
  return { min(ot.minhr, ob.minhr), max(ot.maxhr, ob.maxhr) };
}

const int sn = 1 << 18;
sdata s[2 * sn];
operation o[sn];

void apply(int x, operation op) {
  s[x] = calculate(op, s[x]);
  if (x < sn)
    o[x] = merge(op, o[x]);
}

void push(int x) {
  apply(x << 1, o[x]);
  apply(x << 1 | 1, o[x]);
  o[x] = operation();
}

sdata query(int a, int b, int l = 0, int r = sn, int x = 1) {
  if (b <= l || r <= a)
    return sdata();
  if (a <= l && r <= b)
    return s[x];
  push(x);
  return combine(query(a, b, l, (l + r) / 2, x << 1), query(a, b, (l + r) / 2, r, x << 1 | 1));
}

void apply(int a, int b, operation op, int l = 0, int r = sn, int x = 1) {
  if (b <= l || r <= a)
    return;
  if (a <= l && r <= b)
    return apply(x, op);
  push(x);
  apply(a, b, op, l, (l + r) / 2, x << 1);
  apply(a, b, op, (l + r) / 2, r, x << 1 | 1);
  s[x] = combine(s[x << 1], s[x << 1 | 1]);
}

void update(int x, int minhl, int maxhl) {
  apply(x, x + 1, operation());
  x += sn;
  s[x].minhl = minhl;
  s[x].maxhl = maxhl;
  while (x >>= 1)
    s[x] = combine(s[x << 1], s[x << 1 | 1]);
}

int n, q, h[200100], a[200100], b[200100], l[200100], r[200100], res[200100];
vector<int> actl[200100], deactl[200100], qur[200100];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> h[i] >> a[i] >> b[i];
    actl[min(i + a[i], n)].push_back(i);
    deactl[min(i + b[i] + 1, n)].push_back(i);
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> l[i] >> r[i], l[i]--, r[i]--;
    qur[r[i]].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    for (int j : actl[i])
      update(j, h[j], h[j]);
    for (int j : deactl[i])
      update(j, inf, -inf);
    apply(max(0, i - b[i]), max(0, i - a[i] + 1), { h[i], h[i] });
    for (int j : qur[i])
      res[j] = query(l[j], i).maxcost;
  }
  for (int i = 0; i < q; i++)
    cout << res[i] << "\n";
}

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