Submission #235676

#	Time	Username	Problem	Language	Result	Execution time	Memory
235676		fedoseevtimofey	Two Antennas (JOI19_antennas)	C++14	100 / 100	788 ms	48520 KiB

antennas

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
 
using namespace std;
 
typedef long long ll;

const int N = 2e5 + 7;
const int Inf = 1e9 + 7;

struct Tree {
  int mx[4 * N], t[4 * N], mod[4 * N];

  void update(int v, int x) {
    mod[v] = max(mod[v], x);
    mx[v] = max(mx[v], t[v] + mod[v]);
  }

  void push(int v) {
    if (mod[v] != -Inf) {
      if (2 * v + 1 < 4 * N) update(2 * v + 1, mod[v]);
      if (2 * v + 2 < 4 * N) update(2 * v + 2, mod[v]);
      mod[v] = -Inf;
    }
  }

  void modify(int ql, int qr, int val, int l, int r, int v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      update(v, val);
    } else {
      push(v);
      int m = (l + r) >> 1;
      modify(ql, qr, val, l, m, 2 * v + 1);
      modify(ql, qr, val, m + 1, r, 2 * v + 2);
      t[v] = max(t[2 * v + 1], t[2 * v + 2]);
      mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
    }
  }


  void set_(int id, int val, int l, int r, int v) {
    if (l == r) {
      push(v);
      t[v] = val;
    } else {
      push(v);
      int m = (l + r) >> 1;
      if (id <= m) set_(id, val, l, m, 2 * v + 1);
      else set_(id, val, m + 1, r, 2 * v + 2);
      t[v] = max(t[2 * v + 1], t[2 * v + 2]);
      mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
    }
  }

  int get(int ql, int qr, int l, int r, int v) {
    if (qr < l || r < ql) return -Inf;
    if (ql <= l && r <= qr) return mx[v];
    push(v);
    int m = (l + r) >> 1;
    return max(get(ql, qr, l, m, 2 * v + 1), get(ql, qr, m + 1, r, 2 * v + 2));
  }
  
  Tree() {
    fill(t, t + 4 * N, -Inf);
    fill(mx, mx + 4 * N, -Inf);
    fill(mod, mod + 4 * N, -Inf);
  }
};


vector <int> solve(int n, vector <int> h, vector <int> a, vector <int> b, int q, vector <int> ql, vector <int> qr) {
  vector <vector <pair <int, int>>> who(n);
  vector <int> ans(q, -1);

  for (int i = 0; i < q; ++i) {
    who[qr[i]].emplace_back(ql[i], i);
  }

  vector <vector <int>> add(n), del(n);
  for (int i = 0; i < n; ++i) {
    int l = i + a[i], r = i + b[i];
    r = min(r, n - 1);
    if (l <= r) {
      add[l].push_back(i);
      del[r].push_back(i);
    }
  }

  Tree neg;

  for (int i = 0; i < n; ++i) {
    for (int id : add[i]) {
      neg.set_(id, -h[id], 0, n - 1, 0);
    }
    int l = max(0, i - b[i]);
    int r = i - a[i];
    if (l <= r) {
      neg.modify(l, r, h[i], 0, n - 1, 0);
    }
    for (auto p : who[i]) {
      ans[p.second] = max(ans[p.second], neg.get(p.first, i, 0, n - 1, 0));
    }
    for (int id : del[i]) {
      neg.set_(id, -Inf, 0, n - 1, 0);
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector <int> h(n), a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> h[i] >> a[i] >> b[i];
  }
  int q;
  cin >> q;
  vector <int> ql(q), qr(q);
  for (int i = 0; i < q; ++i) {
    cin >> ql[i] >> qr[i];
    --ql[i], --qr[i];
  }
  vector <int> ans = solve(n, h, a, b, q, ql, qr);
  reverse(h.begin(), h.end());
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  for (int i = 0; i < q; ++i) {
    ql[i] = n - ql[i] - 1;
    qr[i] = n - qr[i] - 1;
    swap(ql[i], qr[i]);
  }
  vector <int> rans = solve(n, h, a, b, q, ql, qr);
  for (int i = 0; i < q; ++i) {
    cout << max(ans[i], rans[i]) << '\n';
  }
}

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