Submission #235661

#	Time	Username	Problem	Language	Result	Execution time	Memory
235661		fedoseevtimofey	Two Antennas (JOI19_antennas)	C++14	24 / 100	3070 ms	26612 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;

struct Tree {
  int t[4 * N];
  
  void modify(int id, int val, int l, int r, int v) {
    if (l == r) {
      t[v] = val;
    } else {
      int m = (l + r) >> 1;
      if (id <= m) modify(id, val, l, m, 2 * v + 1);
      else modify(id, val, m + 1, r, 2 * v + 2);
      t[v] = max(t[2 * v + 1], t[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 t[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);
  }
};

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;
  while (q--) {
    int ql, qr;
    cin >> ql >> qr;
    --ql, --qr;
    vector <vector <int>> add(n), del(n);
    for (int i = ql; i <= qr; ++i) {
      //add[max(0, i - b[i])].push_back(i);
      //del[max(0, i - a[i])].push_back(i);
      int l = i + a[i], r = i + b[i];
      r = min(r, qr);
      if (l <= r) {
        add[l].push_back(i);
        del[r].push_back(i);
      }
    }
    Tree pos, neg;
    int ans = -1;
    for (int i = ql; i <= qr; ++i) {
      for (int id : add[i]) {
        pos.modify(id, h[id], 0, n - 1, 0);
        neg.modify(id, -h[id], 0, n - 1, 0);
      }
      int l = max(ql, i - b[i]);
      int r = i - a[i];
      if (l <= r) {
        ans = max(ans, h[i] + neg.get(l, r, 0, n - 1, 0));
        ans = max(ans, -h[i] + pos.get(l, r, 0, n - 1, 0));
      }
      for (int id : del[i]) {
        pos.modify(id, -Inf, 0, n - 1, 0);
        neg.modify(id, -Inf, 0, n - 1, 0);
      }
    }
    cout << ans << '\n';
  }
}

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