Submission #1154202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154202		fryingduc	Two Antennas (JOI19_antennas)	C++20	0 / 100	253 ms	34884 KiB

antennas

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int inf = 1e9 + 100;
int n, a[maxn], b[maxn], h[maxn];
int ql[maxn], qr[maxn], q;
int res[maxn];
vector<int> ev[maxn];
vector<pair<int, int>> qq[maxn];

pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
  return make_pair(min(a.first, b.first), max(a.second, b.second));
}

struct segment_tree {
  pair<int, int> tree[maxn << 2];
  int lazy[maxn << 2];
  
  segment_tree() {
    for (int i = 1; i <= n * 4; ++i) {
      tree[i] = make_pair(inf, -inf);
      lazy[i] = 0;
    }
  }
  
  void down(int ind, int l, int r) {
    tree[ind].second = max(tree[ind].second, lazy[ind] - tree[ind].first);
    if (l != r) {
      lazy[ind << 1] = max(lazy[ind << 1], lazy[ind]);
      lazy[ind << 1 | 1] = max(lazy[ind << 1 | 1], lazy[ind]);
    }
    lazy[ind] = 0;
  }
  
  void update(int x, int y, int val, int ind = 1, int l = 1, int r = n) {
    if (lazy[ind]) down(ind, l, r);
    if (l > y || r < x) return;
    if (x <= l and r <= y) {
      lazy[ind] = val;
      down(ind, l, r);
      return;
    }
    int mid = (l + r) >> 1;
    update(x, y, val, ind << 1, l, mid);
    update(x, y, val, ind << 1 | 1, mid + 1, r);
    tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
  }
  
  void assign(int pos, int val, int ind = 1, int l = 1, int r = n) {
    if (lazy[ind]) down(ind, l, r);
    if (l > pos || r < pos) return;
    if (l == r) {
      tree[ind].first = val;
      return;
    }
    int mid = (l + r) >> 1;
    assign(pos, val, ind << 1, l, mid);
    assign(pos, val, ind << 1 | 1, mid + 1, r);
    tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
  }
  
  pair<int, int> get(int x, int y, int ind = 1, int l = 1, int r = n) {
    if (lazy[ind]) down(ind, l, r);
    if (l > y || r < x) return make_pair(inf, -inf);
    if (x <= l and r <= y) {
      return tree[ind];
    }
    int mid = (l + r) >> 1;
    return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
  }
} st;



void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> h[i] >> a[i] >> b[i];
  }
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> ql[i] >> qr[i];
    res[i] = -1;
  }
  for (int ite = 0; ite < 2; ++ite) {
    for (int i = 1; i <= n + 1; ++i) {
      ev[i].clear();
      qq[i].clear();
    }
    for (int i = 1; i <= n; ++i) {
      int l = i + a[i], r = min(n, i + b[i]);
      if (l <= n) {
        ev[l].push_back(i);
        ev[r + 1].push_back(-i);
      }
    }
    for (int i = 1; i <= q; ++i) {
      qq[qr[i]].emplace_back(ql[i], i);
    }
    st = segment_tree();
    for (int i = 1; i <= n; ++i) {
      for (auto j:ev[i]) {
        if (j > 0) {
          st.assign(j, h[j]);
        } else {
          st.assign(-j, inf);
        }
      }
      int l = max(1, i - b[i]), r = i - a[i];
      if (r >= 1) {
        st.update(l, r, h[i]);
      }
      for (auto j:qq[i]) {
        res[j.second] = max(res[j.second], st.get(j.first, i).second);
      }
    }
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);
    reverse(h + 1, h + n + 1);
    for (int i = 1; i <= q; ++i) {
      ql[i] = n - ql[i] + 1, qr[i] = n - qr[i] + 1;
      swap(ql[i], qr[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << res[i] << "\n";
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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