제출 #1127940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127940		zNatsumi	Two Antennas (JOI19_antennas)	C++20	100 / 100	777 ms	52592 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ii = pair<int, int>;

const int N = 2e5 + 5;
const long long INF = 1e16;

int n, q, H[N], A[N], B[N], L[N], R[N], res[N];
vector<ii> query[N], quest[N];

struct node{
  int v, a, b;
  node() {}
  node(int v, int a, int b): v(v), a(a), b(b) {}

  friend node operator + (node l, node r){
    return node(max(l.v, r.v), max(l.a, r.a), max(l.b, r.b));
  }
};

struct IT{
  node st[N << 2];
  int lz[N << 2];

  void build(int tl, int tr, int i){
    lz[i] = -INF;
    st[i] = {-2*INF, -INF, -INF};
    if(tl == tr) return;
    int tm = tl + tr >> 1;
    build(tl, tm, i<<1);
    build(tm + 1, tr, i<<1|1);
  }
  void push(int i){
    if(lz[i] == -INF) return;
    st[i<<1].b = max(st[i<<1].b, lz[i]);  st[i<<1|1].b = max(st[i<<1|1].b, lz[i]);
    lz[i<<1] = max(lz[i<<1], lz[i]);      lz[i<<1|1] = max(lz[i<<1|1], lz[i]);

    st[i<<1].v = max(st[i<<1].v, st[i<<1].a + lz[i]);
    st[i<<1|1].v = max(st[i<<1|1].v, st[i<<1|1].a + lz[i]);
    lz[i] = -INF;
  }

  void updateA(int pos, int val, int tl, int tr, int i){
    if(tl == tr){
      st[i].a = val;
      st[i].b = -INF;
      return;
    }
    push(i);
    int tm = tl + tr >> 1;
    if(pos <= tm) updateA(pos, val, tl, tm, i<<1);
    else updateA(pos, val, tm + 1, tr, i<<1|1);
    auto tmp = st[i].v;
    st[i] = st[i<<1] + st[i<<1|1];
    st[i].v = max(st[i].v, tmp);
  }
  void updateB(int l, int r, int val, int tl, int tr, int i){
    if(r < tl || tr < l || l > r) return;
    if(l <= tl && tr <= r){
      st[i].b = max(st[i].b, val);
      lz[i] = max(lz[i], val);
      st[i].v = max(st[i].v, st[i].a + val);
      return;
    }
    push(i);
    int tm = tl + tr >> 1;
    updateB(l, r, val, tl, tm, i<<1);
    updateB(l, r, val, tm + 1, tr, i<<1|1);
    auto tmp = st[i].v;
    st[i] = st[i<<1] + st[i<<1|1];
    st[i].v = max(st[i].v, tmp);
  }
  node get(int l, int r, int tl, int tr, int i){
    if(r < tl || tr < l || l > r) return node(-2*INF, -INF, -INF);
    if(l <= tl && tr <= r) return st[i];
    push(i);
    int tm = tl + tr >> 1;
    return get(l, r, tl, tm, i<<1) + get(l, r, tm + 1, tr, i<<1|1);
  }
} it;



void solve(){
  for(int i = 1; i <= n; i++){
    if(i + A[i] <= n) quest[i + A[i]].emplace_back(1, i);
    if(i + B[i] + 1 <= n) quest[i + B[i] + 1].emplace_back(0, i);
  }
  for(int i = 1; i <= q; i++) query[R[i]].emplace_back(L[i], i);

  it.build(1, n, 1);
  for(int i = 1; i <= n; i++){
    for(auto [ty, idx] : quest[i]){
      if(ty) it.updateA(idx, H[idx], 1, n, 1);
      else it.updateA(idx, -INF, 1, n, 1);
    }
    int l = max(i - B[i], 1LL), r = i - A[i];
    if(l <= r) it.updateB(l, r, -H[i], 1, n, 1);

    for(auto [L, idx] : query[i]){
      auto tmp = it.get(L, i, 1, n, 1);
      res[idx] = max(res[idx], tmp.v);
    }
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  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 >> L[i] >> R[i];

  memset(res, -1, sizeof res);
  for(int _ = 0; _ <= 1; _++){
    solve();
    reverse(H + 1, H + n + 1);
    reverse(A + 1, A + n + 1);
    reverse(B + 1, B + n + 1);
    for(int i = 1; i <= n; i++){
      quest[i].clear();
      query[i].clear();
    }
    for(int i = 1; i <= q; i++){
      auto nL = n - R[i] + 1, nR = n - L[i] + 1;
      L[i] = nL;
      R[i] = nR;
    }
  }
  for(int i = 1; i <= q; i++) cout << (res[i] < 0 ? -1 : res[i]) << "\n";
}

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