Submission #366223

#	Time	Username	Problem	Language	Result	Execution time	Memory
366223		Kazalika	Two Antennas (JOI19_antennas)	C++14	100 / 100	1027 ms	42660 KiB

antennas

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

typedef long long ll;

const int inf = 1e9 + 9;

struct segment_tree {
  int size;
  vector<int> D, C, H;
  segment_tree() {}
  segment_tree(int sz) {
    size = sz;
    D.resize(4 * size, -inf);
    C.resize(4 * size, -inf);
    H.resize(4 * size, -inf);
  }
  void push(int t, int l, int r) {
    D[t] = max(D[t], C[t] + H[t]);
    if (l + 1 != r) {
      H[t * 2 + 1] = max(H[t * 2 + 1], H[t]);
      H[t * 2 + 2] = max(H[t * 2 + 2], H[t]);
    }
    H[t] = -inf;
  }
  void set_C(int t, int l, int r, int id, int vl) {
    push(t, l, r);
    if (l + 1 == r) {
      C[t] = vl;
      D[t] = max(D[t], C[t] + H[t]);
      return;
    }
    int md = r + l >> 1;
    if (md > id)
      set_C(t * 2 + 1, l, md, id, vl);
    else
      set_C(t * 2 + 2, md, r, id, vl);
    D[t] = max({D[t], D[t * 2 + 1], D[t * 2 + 2]});
    C[t] = max(C[t * 2 + 1], C[t * 2 + 2]);
  }
  int get(int t, int l, int r, int x, int y) {
    push(t, l, r);
    if (l >= y || r <= x)
      return -inf;
    if (l >= x && r <= y)
      return D[t];
    int md = r + l >> 1;
    return max(get(t * 2 + 1, l, md, x, y), get(t * 2 + 2, md, r, x, y));
  }
  void set_H(int t, int l, int r, int x, int y, int vl) {
    push(t, l, r);
    if (l >= y || r <= x)
      return;
    if (l >= x && r <= y) {
      H[t] = vl;
      push(t, l, r);
      return;
    }
    int md = r + l >> 1;
    set_H(t * 2 + 1, l, md, x, y, vl);
    set_H(t * 2 + 2, md, r, x, y, vl);
    D[t] = max({D[t], D[t * 2 + 1], D[t * 2 + 2]});
  }

  void set_C(int id, int vl) { set_C(0, 0, size, id, vl); }
  int get(int x, int y) { return get(0, 0, size, x, y + 1); }
  void set_H(int x, int y, int vl) { set_H(0, 0, size, x, y + 1, vl); }
};

const int N = 2e5 + 5;
int n, a[N], b[N], h[N];
int q, l[N], r[N], ans[N];

vector<int> qq[N], add[N], del[N];

void solve() {
  segment_tree sgt(n);
  for (int i = 0; i < n; ++i) {
    for (int id : add[i])
      sgt.set_C(id, -h[id]);
    int L = max(0, i - b[i]);
    int R = i - a[i];
    if (L <= R)
      sgt.set_H(L, R, h[i]);
    for (int id : qq[i])
      ans[id] = max(ans[id], sgt.get(l[id], r[id]));
    for (int id : del[i])
      sgt.set_C(id, -inf);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> h[i] >> a[i] >> b[i];
    if (i + a[i] < n)
      add[i + a[i]].push_back(i);
    if (i + b[i] < n)
      del[i + b[i]].push_back(i);
  }
  cin >> q;
  for (int i = 0; i < q; ++i) {
    cin >> l[i] >> r[i];
    l[i]--, r[i]--;
    qq[r[i]].push_back(i);
    ans[i] = -1;
  }
  solve();
  for (int i = 0; i < n; ++i)
    h[i] = -h[i];
  solve();
  for (int i = 0; i < q; ++i) {
    if (ans[i] < 0)
      cout << "-1\n";
    else
      cout << ans[i] << '\n';
  }
}

Compilation message (stderr)

antennas.cpp: In member function 'void segment_tree::set_C(int, int, int, int, int)':
antennas.cpp:33:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int md = r + l >> 1;
      |              ~~^~~
antennas.cpp: In member function 'int segment_tree::get(int, int, int, int, int)':
antennas.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int md = r + l >> 1;
      |              ~~^~~
antennas.cpp: In member function 'void segment_tree::set_H(int, int, int, int, int, int)':
antennas.cpp:59:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int md = r + l >> 1;
      |              ~~^~~

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