Submission #1292937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292937		LIA	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	2089 ms	119172 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (int i = s; i < e; ++i)

int n;
struct Seg {
  struct Node {
    ll mxval, mxinv;
  };
  v<Node> seg;
  v<ll> lz;
  int sz = 1;
  Seg() {
    for (; sz < n; sz *= 2)
      ;
    seg.resize(2 * sz, {0, 0});
    lz.resize(2 * sz, -1);
  }

  void upd_val(int i, int l, int r, int idx, ll x) {
    if (l == r) {
      seg[i].mxval = x;
      return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid)
      upd_val(i * 2, l, mid, idx, x);
    else
      upd_val(i * 2 + 1, mid + 1, r, idx, x);
    seg[i].mxval = max(seg[i * 2].mxval, seg[i * 2 + 1].mxval);
  }

  void upd_val(int idx, ll x) { upd_val(1, 0, n - 1, idx, x); }

  void upd(int a, int b, ll x) { upd(1, 0, n - 1, a, b, x); }

  void push(int i, int l, int r) {
    ll &add = lz[i];
    if (add) {
      seg[i].mxinv = seg[i].mxval + +add;
      if (l != r) {
        lz[i * 2] = lz[i * 2 + 1] = add;
      }
    }
    add = 0;
  }

  void upd(int i, int l, int r, int a, int b, ll x) {
    if (l > b || r < a)
      return;
    if (l >= a && r <= b) {
      lz[i] = x;
      push(i, l, r);
      return;
    }
    push(i, l, r);
    int mid = (l + r) / 2;
    upd(i * 2, l, mid, a, b, x);
    upd(i * 2 + 1, mid + 1, r, a, b, x);
    seg[i].mxinv = max(seg[i * 2].mxinv, seg[i * 2 + 1].mxinv);
  }

  ll que(int i, int l, int r, int a, int b) {
    if (l > b || r < a)
      return 0;
    push(i, l, r);
    if (l >= a && r <= b) {
      return seg[i].mxinv;
    }
    int mid = (l + r) / 2;
    return max(que(i * 2, l, mid, a, b), que(i * 2 + 1, mid + 1, r, a, b));
  }

  ll que(int a, int b) { return que(1, 0, n - 1, a, b); }
};

int main() {
  int q;
  cin >> n >> q;
  v<ll> arr(n);
  Seg seg;
  lp(i, 0, n) {
    cin >> arr[i];
    seg.upd_val(i, arr[i]);
  }

  v<v<tuple<int, ll, int>>> Q(n);

  lp(i, 0, q) {
    int l, r;
    cin >> l >> r;
    ll k;
    cin >> k;
    l--;
    r--;
    Q[l].push_back({r, k, i});
  }

  v<int> ans(q);
  stack<int> st;

  for (int i = n - 1; i >= 0; --i) {
    while (!st.empty() && arr[st.top()] < arr[i]) {
      st.pop();
    }
    int b = st.empty() ? n : st.top();
    st.push(i);
    if (i + 1 <= b - 1) {
      seg.upd(i + 1, b - 1, arr[i]);
    }

    for (auto C : Q[i]) {
      auto [r, k, idx] = C;
      ll mxinv = seg.que(i, r);
      ans[idx] = (mxinv <= k ? 1 : 0);
    }
  }

  lp(i, 0, q) { cout << ans[i] << '\n'; }

  return 0;
}

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