Submission #1227806

#TimeUsernameProblemLanguageResultExecution timeMemory
1227806luka_zecevicHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++20
100 / 100
857 ms35124 KiB
#include "bits/stdc++.h" #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) using namespace std; const int N = 1e6 + 10; const int INF = 1e9 + 7; int l[N]; int st[4 * N]; bool ans[N]; void update(int index, int l, int r, int val, int pos) { if(l > r || l > pos || r < pos) return; if(l == r) { st[index] = val; return; } int mid = (l + r) / 2; update(index * 2, l, mid, val, pos); update(index * 2 + 1, mid + 1, r, val, pos); st[index] = max(st[index * 2], st[index * 2 + 1]); } int get(int index, int l, int r, int L, int R) { if(l > r || l > R || r < L) return 0; if(l >= L && r <= R) return st[index]; int mid = (l + r) / 2; return max(get(index * 2, l, mid, L, R), get(index * 2 + 1, mid + 1, r, L, R)); } struct upit { int l, r, k, pos; }; upit make_upit(int p) { upit a; cin >> a.l >> a.r >> a.k; a.pos = p; return a; } bool comp(upit a, upit b) { return (a.r < b.r || (a.r == b.r && (a.l < b.l))); } int main() { FAST; int n, q; cin >> n >> q; vector < int > v(n + 1); for(int i = 1; i <= n; i++) cin >> v[i]; v[0] = INF; stack < int > st; st.push(0); for(int i = 1; i <= n; i++) { while(v[st.top()] <= v[i]) st.pop(); l[i] = st.top(); st.push(i); } // for(int i = 1; i <= n; i++) cout << l[i] << " "; // cout << "\n"; vector < upit > t(q); for(int i = 0; i < q; i++) t[i] = make_upit(i + 1); sort(begin(t), end(t), comp); int j = 1; for(auto it : t) { while(j <= it.r) { update(1, 1, n, v[j] + v[l[j]], l[j]); j++; } ans[it.pos] = (get(1, 1, n, it.l, it.r) <= it.k); } for(int i = 1; i <= q; 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...