Submission #989737

#TimeUsernameProblemLanguageResultExecution timeMemory
989737tch1cherinHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
372 ms61552 KiB
#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) { vector<int>().swap(queries); for (int i : queries) { answer[i] = true; } 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 (W[i] > current) { current_inv = max(current_inv, current + W[i]); current = W[i]; } W_val[i] = current_inv; W_max[i] = current; } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...