Submission #681729

#TimeUsernameProblemLanguageResultExecution timeMemory
681729Hacv16Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
1374 ms93824 KiB
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") typedef long long ll; const int MAX = 1e6 + 10; const int INF = 0x3f3f3f3f; struct Q{ ll l, k, id; Q(ll a = 0, ll b = 0, ll c = 0){ l = a, k = b, id = c; } }; ll n, m, a[MAX], seg[4 * MAX]; bool resp[MAX]; vector<Q> queries[MAX]; void update(ll i, ll x, ll p, ll l, ll r){ if(i < l || i > r) return; if(l == r){ seg[p] = max(seg[p], x); return; } ll m = (l + r) >> 1, e = 2 * p, d = e + 1; update(i, x, e, l, m); update(i, x, d, m + 1, r); seg[p] = max(seg[e], seg[d]); } ll query(ll a, ll b, ll p, ll l, ll r){ if(a > r || b < l) return -INF; if(a <= l && r <= b) return seg[p]; ll m = (l + r) >> 1, e = 2 * p, d = e + 1; return max(query(a, b, e, l, m), query(a, b, d, m + 1, r)); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= m; i++){ ll l, r, k; cin >> l >> r >> k; queries[r].emplace_back(l, k, i); } a[0] = INF; stack<int> s; s.push(0); for(int i = 1; i <= n; i++){ while(a[s.top()] <= a[i]) s.pop(); if(s.top() != 0){ int idx = s.top(); update(idx, a[idx] + a[i], 1, 1, n); } s.push(i); for(auto q : queries[i]){ int l = q.l, k = q.k, idx = q.id; resp[idx] = (query(l, i, 1, 1, n) <= k); } } for(int i = 1; i <= m; i++) cout << resp[i] << '\n'; exit(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...