Submission #218872

#	Time	Username	Problem	Language	Result	Execution time	Memory
218872		rama_pang	Two Antennas (JOI19_antennas)	C++14	100 / 100	744 ms	36800 KiB

antennas

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

const int INF = 1e9 + 100;

class SegmentTree {
 private:
  int sz;
  vector<int> C; // C[i] = H[i] if i is active, -INF otherwise. We hold maximum C for each node.
  vector<int> D; // D[i] = max(C[i] - H[j]) so far. We hold maximum D for each node.
  vector<int> L; // lazy propagation, we have to update D[k] = max(D[k], C[k] - L) on segment

  void Push(int n) {
    if (L[n] != INF) {
      L[n * 2] = min(L[n * 2], L[n]); // in order to maximize C[k] - L
      L[n * 2 + 1] = min(L[n * 2 + 1], L[n]);

      D[n * 2] = max(D[n * 2], C[n * 2] - L[n]); // lazy propagation
      D[n * 2 + 1] = max(D[n * 2 + 1], C[n * 2 + 1] - L[n]);

      L[n] = INF;
    }
  }

  void Pull(int n) {
    C[n] = max(C[n * 2], C[n * 2 + 1]); // C helps in lazy propagation to update maximum C - L quickly
    D[n] = max(D[n * 2], D[n * 2 + 1]);
  }

  void PointSetUpdate(int n, int tl, int tr, int k, int H) {
    if (tl == tr) return void(C[n] = H);
    Push(n);
    int mid = (tl + tr) / 2;
    if (k <= mid) {
      PointSetUpdate(n * 2, tl, mid, k, H);
    } else {
      PointSetUpdate(n * 2 + 1, mid + 1, tr, k, H);
    }
    Pull(n);
  }

  void RangeUpdate(int n, int tl, int tr, int l, int r, int H) {
    if (tr < l || r < tl || tl > tr || l > r) return;
    if (l <= tl && tr <= r) {
      D[n] = max(D[n], C[n] - H);
      L[n] = min(L[n], H);
      return;
    }
    Push(n);
    int mid = (tl + tr) / 2;
    RangeUpdate(n * 2, tl, mid, l, r, H);
    RangeUpdate(n * 2 + 1, mid + 1, tr, l, r, H);
    Pull(n);
  }

  int RangeMaximumQuery(int n, int tl, int tr, int l, int r) {
    if (tr < l || r < tl || tl > tr || l > r) return -INF;
    if (l <= tl && tr <= r) return D[n];
    Push(n);
    int mid = (tl + tr) / 2;
    return max(RangeMaximumQuery(n * 2, tl, mid, l, r), 
                RangeMaximumQuery(n * 2 + 1, mid + 1, tr, l, r));
  }
  
 public:
  SegmentTree(int n) : sz(n) {
    C.assign(4 * sz, -INF);
    D.assign(4 * sz, -INF);
    L.assign(4 * sz, INF);
  }

  void PointSetUpdate(int k, int H) { // set C[k] = H
    return PointSetUpdate(1, 0, sz - 1, k, H);
  }

  void RangeUpdate(int l, int r, int H) { // for each k, l <= k <= r, D[k] = max(D[k], C[k] - H)
    return RangeUpdate(1, 0, sz - 1, l, r, H);
  }

  int RangeMaximumQuery(int l, int r) { // RMQ on the array D
    return RangeMaximumQuery(1, 0, sz - 1, max(l, 0), r);
  }
};

vector<int> answer;

void Solve(int N, int Q, vector<int> H, vector<int> A, vector<int> B, 
            vector<int> L, vector<int> R) {
  
  int a;
  vector<vector<pair<int, int>>> events(N); // (type, x)
  // type = 1  -> set C[x] = H[x]
  // type = 2 -> set C[x] = -INF
  // type <= 0  -> query (x, current), query id is -type

  for (int i = 0; i < N; i++) {
    int l = i + A[i], r = i + B[i] + 1; // antenna i is active on segment [l, r)
    if (l < N) events[l].emplace_back(1, i);
    if (r < N) events[r].emplace_back(2, i);
  }

  for (int i = 0; i < Q; i++) {
    events[R[i]].emplace_back(-i, L[i]);
  }

  SegmentTree seg(N);

  for (int t = 0; t < N; t++) {
    reverse(begin(events[t]), end(events[t]));

    while (!events[t].empty()) { // updates
      if (events[t].back().first <= 0) break;
      int type = events[t].back().first;
      int x = events[t].back().second;
      events[t].pop_back();

      if (type == 1) {
        seg.PointSetUpdate(x, H[x]);
      } else {
        seg.PointSetUpdate(x, -INF);
      }
    }

    // for k, t - B[t] <= k <= t - A[t], we update D[k] = max(D[k], C[k] - H[t])
    seg.RangeUpdate(t - B[t], t - A[t], H[t]);

    while (!events[t].empty()) { // queries
      int ql = events[t].back().second;
      int qr = t;
      int qi = -events[t].back().first;
      events[t].pop_back();
      answer[qi] = max(answer[qi], seg.RangeMaximumQuery(ql, qr));
    }
  }
}

void Solve() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  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> L(Q), R(Q);
  for (int i = 0; i < Q; i++) {
    cin >> L[i] >> R[i];
    L[i]--, R[i]--;
  }

  answer.assign(Q, -1);

  auto Reverse = [&]() {
    // reverse the array
    reverse(begin(H), end(H));
    reverse(begin(A), end(A));
    reverse(begin(B), end(B));
    for (int i = 0; i < Q; i++) {
      L[i] = N - 1 - L[i];
      R[i] = N - 1 - R[i];
      swap(L[i], R[i]);
    }
  };

  Solve(N, Q, H, A, B, L, R);
  Reverse();
  Solve(N, Q, H, A, B, L, R);
}

void Write() {
  for (auto &ans : answer) {
    cout << ans << "\n";
  }
}

int main() {
  Solve();
  Write();
  return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'void Solve(int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
antennas.cpp:90:7: warning: unused variable 'a' [-Wunused-variable]
   int a;
       ^

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