Submission #200066

#	Time	Username	Problem	Language	Result	Execution time	Memory
200066		EntityIT	Two Antennas (JOI19_antennas)	C++14	100 / 100	812 ms	37496 KiB

antennas

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const int inf = 1e9 + 7;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int n;
vector<tuple<int, int, int> > antennas;

struct Node {
  int ans, mnH, mxH;
  Node(int _ans = -1, int _mnH = inf, int _mxH = -inf) : ans(_ans), mnH(_mnH), mxH(_mxH) {}

  Node operator + (const Node &_) const { return Node(max(ans, _.ans), min(mnH, _.mnH), max(mxH, _.mxH) );}
};

struct Lz {
  int mnH, mxH;
  Lz(int _mnH = inf, int _mxH = -inf) : mnH(_mnH), mxH(_mxH) {}

  bool operator == (const Lz &_) const { return mnH == _.mnH && mxH == _.mxH; }

  Lz& operator += (const Lz& _) { asMn(mnH, _.mnH); asMx(mxH, _.mxH); return *this; }
};

struct It {
  vector<Node> node;
  vector<Lz> lz;
  It(int nNode) {
    node.assign(nNode, Node() );
    lz.assign(nNode, Lz() );
  }

  void trueVal(int i, int Left, int Right) {
    if (lz[i] == Lz() ) return ;

    if (node[i].mnH < inf) {
      asMx(node[i].ans, abs(lz[i].mnH - node[i].mxH) );
      asMx(node[i].ans, abs(lz[i].mxH - node[i].mnH) );
    }

    if (Left != Right) {
      lz[i << 1] += lz[i];
      lz[i << 1 | 1] += lz[i];
    }

    lz[i] = Lz();
  }

  void ins(int pos, int i = 1, int Left = 0, int Right = n - 1) {
    trueVal(i, Left, Right);
    if (pos < Left || Right < pos) return ;
    if (Left == Right) {
      node[i].mnH = node[i].mxH = get<0>(antennas[pos]);
      return ;
    }
    int Mid = (Left + Right) >> 1;
    ins(pos, i << 1, Left, Mid);
    ins(pos, i << 1 | 1, Mid + 1, Right);

    node[i] = node[i << 1] + node[i << 1 | 1];
  }

  void era(int pos, int i = 1, int Left = 0, int Right = n - 1) {
    trueVal(i, Left, Right);
    if (pos < Left || Right < pos) return ;
    if (Left == Right) {
      node[i].mnH = inf; node[i].mxH = -inf;
      return ;
    }
    int Mid = (Left + Right) >> 1;
    era(pos, i << 1, Left, Mid);
    era(pos, i << 1 | 1, Mid + 1, Right);

    node[i] = node[i << 1] + node[i << 1 | 1];
  }

  void upd(int l, int r, int h, int i = 1, int Left = 0, int Right = n - 1) {
    trueVal(i, Left, Right);
    if (r < Left || Right < l) return ;
    if (l <= Left && Right <= r) {
      lz[i] = Lz(h, h); trueVal(i, Left, Right);
      return ;
    }
    int Mid = (Left + Right) >> 1;
    upd(l, r, h, i << 1, Left, Mid);
    upd(l, r, h, i << 1 | 1, Mid + 1, Right);

    node[i] = node[i << 1] + node[i << 1 | 1];
  }

  int getAns(int l, int r, int i = 1, int Left = 0, int Right = n - 1) {
    trueVal(i, Left, Right);
    if (r < Left || Right < l) return -1;
    if (l <= Left && Right <= r) return node[i].ans;
    int Mid = (Left + Right) >> 1;
    return max(getAns(l, r, i << 1, Left, Mid), getAns(l, r, i << 1 | 1, Mid + 1, Right) );
  }
};

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

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  cin >> n;
  antennas.assign(n, {} );
  vector<vector<pair<int, bool> > > change(n);
  for (int i = 0; i < n; ++i) {
    cin >> get<0>(antennas[i]) >> get<1>(antennas[i]) >> get<2>(antennas[i]);
    if (i + get<1>(antennas[i]) < n) change[i + get<1>(antennas[i])].emplace_back(i, true);
    if (i + get<2>(antennas[i]) + 1 < n) change[i + get<2>(antennas[i]) + 1].emplace_back(i, false);
  }

  int q; cin >> q;
  vector<vector<pair<int, int> > > que(n);
  for (int i = 0; i < q; ++i) {
    int l, r; cin >> l >> r; --l; --r;
    que[r].emplace_back(l, i);
  }

  It it( (n + 5) << 2);
  vector<int> ans(q);
  for (int r = 0; r < n; ++r) {
    for (auto _ : change[r]) {
      int pos = _.first; bool ins = _.second;
      if (ins) it.ins(pos);
      else it.era(pos);
    }

    it.upd(r - get<2>(antennas[r]), r - get<1>(antennas[r]), get<0>(antennas[r]) );

    for (auto _ : que[r]) {
      int l = _.first, id = _.second;
      ans[id] = it.getAns(l, r);
    }
  }

  for (auto i : ans) cout << i << '\n';

  return 0;
}

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