Submission #866569

#TimeUsernameProblemLanguageResultExecution timeMemory
866569nima_aryanHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
823 ms104100 KiB
/** * author: NimaAryan * created: 2023-10-26 14:32:00 **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #endif using i64 = long long; struct Item { int max_pair; }; Item operator+(Item a, Item b) { if (b.max_pair > a.max_pair) { swap(a, b); } return a; } struct Fenwick { vector<Item> fenw; int n; Fenwick(int n) : n(n) { fenw.resize(n); } void modify(int x, Item v) { for (int i = x + 1; i <= n; i += i & -i) { fenw[i - 1] = fenw[i - 1] + v; } } Item query(int x) { Item res{}; for (int i = x; i > 0; i -= i & -i) { res = res + fenw[i - 1]; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; vector<int> w(N); for (int i = 0; i < N; ++i) { cin >> w[i]; } vector<int> l(M), r(M), k(M); vector<vector<int>> qs(N); for (int i = 0; i < M; ++i) { cin >> l[i] >> r[i] >> k[i]; --l[i], --r[i]; qs[r[i]].push_back(i); } vector<int> L(N), stk; for (int i = 0; i < N; ++i) { while (!stk.empty() && w[stk.back()] < w[i]) { stk.pop_back(); } L[i] = stk.empty() ? -1 : stk.back(); stk.push_back(i); } Fenwick fen(N + 1); // i -> N-i-1 vector<int> ans(M); for (int r = 0; r < N; ++r) { if (L[r] != -1) { fen.modify(N - L[r] - 1, Item{w[r] + w[L[r]]}); } for (int i : qs[r]) { ans[i] = fen.query(N - l[i]).max_pair <= k[i]; } } for (int i = 0; i < M; ++i) { cout << ans[i] << "\n"; } return 0; }
#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...