Submission #989717

#	Time	Username	Problem	Language	Result	Execution time	Memory
989717		tch1cherin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1780 ms	66448 KiB

sortbooks

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

const int MAX_N = 1000000;
int W[MAX_N], W_val[MAX_N], W_inv[MAX_N], buff[MAX_N], buff_pos[MAX_N];
int L[MAX_N], R[MAX_N], K[MAX_N];
bool answer[MAX_N];

inline int fast_max(int a, int b) {
  return a > b ? a : b;
}

void divide(vector<int>& queries, int left, int right) {
  if (right - left == 1) {
    for (int i : queries) {
      answer[i] = true;
    }
    vector<int>().swap(queries);
    return;
  }
  int mid = (left + right) / 2;
  vector<int> q_left, q_mid, q_right;
  for (int i : queries) {
    if (R[i] < mid) {
      q_left.push_back(i);
    } else if (L[i] >= mid) {
      q_right.push_back(i);
    } else {
      q_mid.push_back(i);
    }
  }
  vector<int>().swap(queries);
  divide(q_left, left, mid); 
  divide(q_right, mid, right);
  int current = -1e9, current_inv = 0;
  for (int i = mid - 1; i >= left; i--) {
    if (current < W[i]) {
      current_inv = max(current_inv, current + W[i]);
      current = W[i];
    }
    W_val[i] = current;
    W_inv[i] = current_inv;
  }
  current = current_inv = 0;
  set<int> S; // wanted to do O((N + M) * (log(N) + log(M))) but log^2 is ok
  for (int i = mid, j = 0; i < right; i++) {
    S.insert(W[i]);
    current = fast_max(current, W[i]);
    if (W[i] < current) {
      current_inv = fast_max(current_inv, W[i] + current);
    }
    while (j < (int)q_mid.size() && R[q_mid[j]] == i) {
      int q = q_mid[j];
      int min_k = max(current_inv, W_inv[L[q]]);
      auto it = S.lower_bound(W_val[L[j]]);
      if (it != S.begin()) {
        min_k = max(min_k, *prev(it) + W_val[L[j]]);
      }
      answer[q] = min_k <= K[q];
      j++;
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    cin >> W[i];
  }
  for (int i = 0; i < M; i++) {
    cin >> L[i] >> R[i] >> K[i];
    L[i]--, R[i]--;
  }
  vector<int> queries(M);
  iota(queries.begin(), queries.end(), 0);
  sort(queries.begin(), queries.end(), [](int x, int y) { return R[x] < R[y]; });
  divide(queries, 0, N);
  for (int i = 0; i < M; i++) {
    cout << int(answer[i]) << "\n";
  }
}

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