Submission #952352

#	Time	Username	Problem	Language	Result	Execution time	Memory
952352		ind1v	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	77 / 100	2611 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
const int L = 20;

int n, m;
int w[N], rx[L][N];
int mx[L][N], lg2[N];
int mxr[L][N];

int rmx(int l, int r) {
  int w = lg2[r - l + 1];
  return max(mx[w][l], mx[w][r - (1 << w) + 1]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 2; i < N; i++) {
    lg2[i] = lg2[i >> 1] + 1;
  }
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    mx[0][i] = w[i];
  }
  stack<int> st;
  for (int i = n; i >= 1; i--) {
    while (!st.empty() && w[i] > w[st.top()]) {
      st.pop();
    }
    rx[0][i] = (st.empty() ? n + 1 : st.top());
    st.push(i);
  }
  rx[0][n + 1] = n + 1;
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n + 1; i++) {
      rx[j][i] = rx[j - 1][rx[j - 1][i]];
    }
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
    }
  }
  for (int i = 1; i <= n + 1; i++) {
    if (rx[0][i] > i + 1) {
      mxr[0][i] = w[i] + rmx(i + 1, rx[0][i] - 1);
    }
  }
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n + 1; i++) {
      mxr[j][i] = max(mxr[j - 1][i], mxr[j - 1][rx[j - 1][i]]);
    }
  }
  while (m--) {
    int l, r, k;
    cin >> l >> r >> k;
    bool f = true;
    for (int i = L - 1; i >= 0; i--) {
      if (rx[i][l] <= r) {
        f &= (mxr[i][l] <= k);
        l = rx[i][l];
      }
    }
    if (l < r) {
      f &= (w[l] + rmx(l + 1, r) <= k);
    }
    cout << f << '\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: 0 / 23