Submission #1161123

#TimeUsernameProblemLanguageResultExecution timeMemory
1161123MisterReaperHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
13 / 100
565 ms75232 KiB
#include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif struct SegmentTree { int n; std::vector<int> tree; SegmentTree(int n_) : n(n_), tree(n << 1) {} void modify(int p, int x) { for (tree[p += n] = x; p > 1; p >>= 1) { tree[p >> 1] = std::max(tree[p], tree[p ^ 1]); } } int query(int l, int r) { int res = 0; for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = std::max(res, tree[l++]); if (r & 1) res = std::max(tree[--r], res); } return res; } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, Q; std::cin >> N >> Q; std::vector<int> A(N); for (int i = 0; i < N; ++i) { std::cin >> A[i]; } std::vector<int> ans(Q); std::vector<std::array<int, 3>> qq(Q); for (int i = 0; i < Q; ++i) { std::cin >> qq[i][0] >> qq[i][1] >> qq[i][2]; --qq[i][0], --qq[i][1]; } std::vector<std::vector<int>> vec(N); for (int i = 0; i < Q; ++i) { vec[qq[i][1]].emplace_back(i); } std::vector<int> stk; SegmentTree seg(N); for (int i = 0; i < N; ++i) { while (!stk.empty() && A[stk.back()] > A[i]) { seg.modify(stk.back(), A[stk.back()] + A[i]); stk.pop_back(); } stk.emplace_back(i); for (auto qi : vec[i]) { ans[qi] = seg.query(qq[qi][0], qq[qi][1]) <= qq[qi][2]; } } for (int i = 0; i < Q; ++i) { std::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...