This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |