제출 #677733

#제출 시각아이디문제언어결과실행 시간메모리
677733AlcabelHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e1, maxlog = 20; int w[maxn], Log[maxn + 1], jump[maxn][maxlog]; struct SparseTable { int n; int st[maxn][maxlog]; SparseTable() {} SparseTable(int _n) { n = _n; } void build() { for (int i = 0; i < n; ++i) { st[i][0] = jump[i][0]; } for (int j = 1; j <= Log[n]; ++j) { for (int i = 0; i + (1 << j) - 1 < n; ++i) { st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } } int getMax(int l, int r) { int j = Log[r - l + 1]; return max(st[l][j], st[r - (1 << j) + 1][j]); } ~SparseTable() {} }; void solve() { int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> w[i]; for (int j = 0; j < maxlog; ++j) { jump[i][j] = -1; } } vector<int> stk; for (int i = 0; i < n; ++i) { while (!stk.empty() && w[i] >= w[stk.back()]) { stk.pop_back(); } if (!stk.empty()) { jump[i][0] = stk.back(); for (int j = 1; j < maxlog && jump[jump[i][j - 1]][j - 1] != -1; ++j) { jump[i][j] = jump[jump[i][j - 1]][j - 1]; } } stk.push_back(i); } SparseTable st(n); st.build(); while (m--) { int l, r, k; cin >> l >> r >> k; --l, --r; int left = -1, right = r + 1; while (right - left > 1) { int mid = left + (right - left) / 2; if (st.getMax(r - mid, r) >= l) { right = mid; } else { left = mid; } } r -= right; // cerr << "r: " << r << '\n'; if (r <= l) { cout << "1\n"; } else { for (int j = maxlog - 1; j >= 0; --j) { if (jump[r][j] != -1 && jump[jump[r][j]][0] >= l) { r = jump[r][j]; } } if (w[r] + w[jump[r][0]] > k) { cout << "0\n"; } else { cout << "1\n"; } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); Log[1] = 0; for (int i = 2; i <= maxn; ++i) { Log[i] = Log[i >> 1] + 1; } int T = 1; // cin >> T; while (T--) { solve(); } 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...