Submission #1096254

#TimeUsernameProblemLanguageResultExecution timeMemory
1096254MuhammetHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
290 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define sz(s) (int)s.size() #define ff first #define ss second #define ll long long const int N = 1e6 + 5; ll n, m, a[N], b[N*4], mmx; vector <vector <ll>> st; void bld(int nd, int l, int r){ if(l == r){ st[nd].push_back(a[l]); return; } int md = (l + r) / 2; bld(nd*2,l,md); bld(nd*2+1,md+1,r); st[nd].resize(sz(st[nd*2]) + sz(st[nd*2+1])); merge(st[nd*2].begin(), st[nd*2].end(), st[nd*2+1].begin(), st[nd*2+1].end(), st[nd].begin()); ll mx = 0; for(int i = l; i <= r; i++){ if(mx > a[i]) b[nd] = max(b[nd],mx+a[i]); mx = max(mx,a[i]); } return; } int fnd(int nd, int l, int r, int x, int y){ if(r < x or l > y) return 0; if(l >= x and r <= y){ int t = lower_bound(st[nd].begin(), st[nd].end(), mmx) - st[nd].begin(); ll k = 0; if(t != 0) k = (mmx+ st[nd][t-1]); k = max(k,b[nd]); mmx = max(mmx,st[nd].back()); return k; } int md = (l + r) / 2; return max(fnd(nd*2,l,md,x,y), fnd(nd*2+1,md+1,r,x,y)); } int main(){ ios::sync_with_stdio (false); cin.tie(nullptr); cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; } st.resize(n*4); bld(1,1,n); for(int i = 1; i <= m; i++){ ll l, r, k; cin >> l >> r >> k; mmx = 0; cout << (fnd(1,1,n,l,r) > k ? 0 : 1) << '\n'; } }
#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...