Submission #395969

#	Time	Username	Problem	Language	Result	Execution time	Memory
395969		rama_pang	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1271 ms	109368 KiB

sortbooks

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

class SegTree {
 public:
  int sz;
  vector<int> tree;

  SegTree(int sz) : sz(sz), tree(2 * sz, 0) {}

  void Modify(int p, int x) {
    for (p += sz; p > 0; p /= 2) tree[p] = max(tree[p], x);
  }

  int Query(int l, int r) {
    int res = 0;
    for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) res = max(res, tree[l++]);
      if (r & 1) res = max(res, tree[--r]);
    }
    return res;
  }
};

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

  int N, Q;
  cin >> N >> Q;

  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  vector<int> ans(Q);
  vector<vector<array<int, 3>>> query(N);
  for (int i = 0; i < Q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    l--, r--;
    query[l].push_back({r, k, i});
  }

  // Solution:
  //
  // For a range [L, R], we want to pick
  // i, j, s.t. L <= i < k <= R, A[i] > A[j],
  // where A[i] + A[j] is maximal. Then, if
  // A[i] + A[j] > k, the books cannot be sorted;
  // otherwise, it can.
  //
  // Note that for i < j, A[i] > A[j], since we can
  // only swap adjacent books, at some point in sorting
  // A[i] and A[j] must be adjacent, and we must swap them.
  //
  // Let's sweep from right to left. Note that for i < j,
  // A[i] > A[j]:
  // - If there exist i < k < j, s.t. A[j] < A[i] < A[k], the pair
  //   (k, j) is strictly better.
  // - If there exist i < k < j, s.t. A[i] > A[k] > A[j], the pair
  //   (i, k) is strictly better.
  //
  // Note that this means, for all (i, j), it is optimal if all indices
  // i < k < j, either A[k] < min(A[i], A[j]) must hold.
  //
  // This means, we only need to care about the nearest element to the left
  // of j which is greater than A[j]. This is only O(N), and can be computed
  // easily.
  //
  // We can answer everything offline in O((N + Q) log N).

  vector<vector<int>> candidates(N);
  { // Compute candidates, (i, j) is good if i is nearest element greater than A[j] to the right
    vector<int> st;
    for (int i = 0; i < N; i++) {
      while (!st.empty() && A[st.back()] <= A[i]) {
        st.pop_back();
      }
      if (!st.empty()) {
        candidates[st.back()].emplace_back(i);
      }
      st.emplace_back(i);
    }
  }

  SegTree seg(N);
  for (int l = N - 1; l >= 0; l--) {
    for (auto r : candidates[l]) {
      seg.Modify(r, A[l] + A[r]);
    }
    for (auto [r, k, q] : query[l]) {
      ans[q] = seg.Query(l, r) <= k;
    }
  }

  for (int i = 0; i < Q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23