Submission #525752

#	Time	Username	Problem	Language	Result	Execution time	Memory
525752		Alex_tz307	Two Antennas (JOI19_antennas)	C++17	100 / 100	729 ms	41880 KiB

antennas

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int kN = 2e5;
int h[1 + kN], a[1 + kN], b[1 + kN], l[1 + kN], r[1 + kN], sol[1 + kN];

struct node {
  int mx, mn, best;
} NIL{-INF, INF, -INF};

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

struct ST {
  int n;
  vector<node> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2, NIL);
  }

  void updateNode(int x, int v) {
    minSelf(t[x].mn, v);
    maxSelf(t[x].best, t[x].mx - t[x].mn);
  }

  void push(int x) {
    if (t[x].mn == INF) {
      return;
    }
    for (int i = 0; i < 2; ++i) {
      updateNode(x * 2 + i, t[x].mn);
    }
    t[x].mn = INF;
  }

  void setMax(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      t[x].mx = v;
      t[x].mn = INF;
      return;
    }
    push(x);
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      setMax(x * 2, lx, mid, pos, v);
    } else {
      setMax(x * 2 + 1, mid + 1, rx, pos, v);
    }
    t[x].mx = max(t[x * 2].mx, t[x * 2 + 1].mx);
    t[x].best = max({t[x].best, t[x * 2].best, t[x * 2 + 1].best, t[x].mx - t[x].mn});
  }

  void setMax(int pos, int v) {
    setMax(1, 1, n, pos, v);
  }

  void updateMin(int x, int lx, int rx, int st, int dr, int v) {
    if (st <= lx && rx <= dr) {
      updateNode(x, v);
      return;
    }
    push(x);
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      updateMin(x * 2, lx, mid, st, dr, v);
    }
    if (mid < dr) {
      updateMin(x * 2 + 1, mid + 1, rx, st, dr, v);
    }
    t[x].mx = max(t[x * 2].mx, t[x * 2 + 1].mx);
    t[x].best = max({t[x].best, t[x * 2].best, t[x * 2 + 1].best, t[x].mx - t[x].mn});
  }

  void updateMin(int st, int dr, int v) {
    updateMin(1, 1, n, st, dr, v);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x].best;
    }
    push(x);
    int mid = (lx + rx) / 2, ans = -1;
    if (st <= mid) {
      maxSelf(ans, query(x * 2, lx, mid, st, dr));
    }
    if (mid < dr) {
      maxSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
    }
    return ans;
  }

  int query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

void solve(int n, int q) {
  vector<vector<int>> queries(n + 1);
  for (int i = 1; i <= q; ++i) {
    queries[r[i]].emplace_back(i);
  }
  vector<vector<int>> enable(n + 1), disable(n + 1);
  ST t(n);
  for (int i = 1; i <= n; ++i) {
    for (int x : enable[i]) {
      t.setMax(x, h[x]);
    }
    for (int x : disable[i]) {
      t.setMax(x, -INF);
    }
    if (i - a[i] >= 1) {
      t.updateMin(max(1, i - b[i]), i - a[i], h[i]);
    }
    for (int j : queries[i]) {
      maxSelf(sol[j], t.query(l[j], i));
    }
    if (i + a[i] <= n) {
      enable[i + a[i]].emplace_back(i);
    }
    if (i + b[i] + 1 <= n) {
      disable[i + b[i] + 1].emplace_back(i);
    }
  }
}

void testCase() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> h[i] >> a[i] >> b[i];
  }
  int q;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> l[i] >> r[i];
    sol[i] = -1;
  }
  solve(n, q);
  reverse(h + 1, h + n + 1);
  reverse(a + 1, a + n + 1);
  reverse(b + 1, b + n + 1);
  for (int i = 1; i <= q; ++i) {
    swap(l[i], r[i]);
    l[i] = n - l[i] + 1;
    r[i] = n - r[i] + 1;
  }
  solve(n, q);
  for (int i = 1; i <= q; ++i) {
    cout << sol[i] << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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