Submission #989747

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989747	2024-05-28T17:29:59 Z	tch1cherin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	504 ms	67700 KB

sortbooks

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 1000000;
int W[MAX_N], L[MAX_N], R[MAX_N], K[MAX_N], W_val[MAX_N], W_max[MAX_N], W_pref[MAX_N];
bool answer[MAX_N];
 
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;
  vector<int> stk;
  for (int i = mid - 1; i >= left; i--) {
    while (!stk.empty() && W[i] > W[stk.back()]) {
      current_inv = max(current_inv, W[i] + W[stk.back()]);
      stk.pop_back();
    }
    stk.push_back(i);
    W_val[i] = current_inv;
    W_max[i] = W[stk[0]];
  }
  current = -1e9, current_inv = 0;
  for (int i = mid; i < right; i++) {
    if (W[i] >= current) {
      current = W[i];
    } else {
      current_inv = max(current_inv, current + W[i]);
    }
    W_val[i] = current_inv;
    W_max[i] = current;
  }
  for (int i = mid - 1, j = mid; i >= left; i--) {
    while (j < right && W[j] < W[i]) {
      j++;
    }
    W_pref[i] = j;
  }
  for (int i = mid, j = 0; i < right; i++) {
    while (j < (int)q_mid.size() && R[q_mid[j]] == i) {
      int min_k = max({W_val[i], W_val[L[q_mid[j]]], W[mid] >= W_max[L[q_mid[j]]] ? 0 : W_max[min(W_pref[L[q_mid[j]]] - 1, i)] + W_max[L[q_mid[j]]]});
      answer[q_mid[j]] = min_k <= K[q_mid[j]];
      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);
  divide(queries, 0, N);
  for (int i = 0; i < M; i++) {
    cout << (int)answer[i] << "\n";
  }
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Incorrect	1 ms	2396 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Incorrect	1 ms	2396 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	467 ms	54624 KB	Output is correct
2	Correct	463 ms	66148 KB	Output is correct
3	Correct	491 ms	64960 KB	Output is correct
4	Correct	504 ms	65300 KB	Output is correct
5	Incorrect	405 ms	67700 KB	Output isn't correct
6	Halted	0 ms	0 KB	-