Submission #168757

#TimeUsernameProblemLanguageResultExecution timeMemory
168757RafaelSusHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
1172 ms27820 KiB
#include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; const int maxn = 1e6 + 6; int a[maxn]; int b[maxn]; int t[maxn * 4]; void build(int v, int tl, int tr){ if (tl == tr){ t[v] = b[tl - 1]; }else{ int tm = (tl + tr) / 2; build (v + v, tl, tm); build (v + v + 1, tm + 1, tr); t[v] = max(t[v + v], t[v + v + 1]); } } int q(int v, int tl, int tr, int l, int r){ if (l > r) return 0; if (tl == l && tr == r)return t[v]; int tm = (tl + tr) / 2; return max(q(v + v, tl, tm, l, min(tm, r)), q(v + v + 1, tm + 1, tr, max(l, tm + 1), r)); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector <int> h; for (int i = 0; i < n; i++){ cin >> a[i]; while (!h.empty() && a[h.back()] <= a[i])h.pop_back(); if (h.empty())h.push_back(i); else{ int idx = h.back(); b[i] = a[idx] + a[i]; } } //for (int i = 0; i < n; i++)cout << b[i] << ' '; //cout << '\n'; build(1, 1, n); for (int i = 0; i < m; i++){ int l, r, mo; cin >> l >> r >> mo; //cout << l << ' ' << r << ' '; //cout << q(1, 1, n, l, r) << ' '; if (q(1, 1, n, l, r) > mo){ cout << "0\n"; }else { cout << "1\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...