Submission #683560

#TimeUsernameProblemLanguageResultExecution timeMemory
683560FatihSolakHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
3034 ms158596 KiB
#include <bits/stdc++.h> #define N 1000005 #define K 20 using namespace std; int len[N]; int maxi[N][K]; int nxt[N]; int a[N]; int ans[N]; struct node{ int val = 0,maxi = -1; }; int gett(int l,int r){ if(r < l) return -1e9; int ln = r-l+1; return max(maxi[l][len[ln]],maxi[r - (1<<len[ln]) + 1][len[ln]]); } struct SegTree{ vector<node> t; int n; SegTree(int sz){ n = sz; t.assign(4*n,{0,0}); build(1,1,n); } node merge(node x,node y){ node ret = x; ret.val = max(ret.val,y.val); if(a[y.maxi] > a[x.maxi]) ret.maxi = y.maxi; return ret; } void build(int v,int tl,int tr){ if(tl == tr){ t[v].maxi = tl; return; } int tm = (tl + tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); t[v] = merge(t[v*2],t[v*2+1]); for(int i = tm+1;i<=tr;i++){ if(a[i] < a[t[v*2].maxi]){ t[v].val = max(t[v].val,a[t[v*2].maxi] + a[i]); } } } node get(int v,int tl,int tr,int l,int r){ if(tr < l || r < tl){ return {0,0}; } if(l <= tl && tr <= r){ return t[v]; } int tm = (tl + tr)/2; node x = get(v*2,tl,tm,l,r); node y = get(v*2+1,tm+1,tr,l,r); if(x.maxi > 0) x.val = max(x.val,a[x.maxi] + gett(max(l,tm+1),min({nxt[x.maxi]-1,r,tr}))); return merge(x,y); } node get(int l,int r){ return get(1,1,n,l,r); } }; void solve(){ int n,m; cin >> n >> m; for(int i = 1;i<=n;i++){ len[i] = len[i-1]; if((1<<(len[i]+1)) < i) len[i]++; cin >> a[i]; maxi[i][0] = a[i]; } for(int j = 1;j<K;j++){ for(int i = 1;i<=n;i++){ if(i + (1<<j) - 1 <= n) maxi[i][j] = max(maxi[i][j-1],maxi[i + (1<<(j-1))][j-1]); } } stack<int> st; st.push(n+1); a[n+1] = 1e9 + 5; for(int i =n;i>=1;i--){ while(a[st.top()] <= a[i]) st.pop(); nxt[i] = st.top(); st.push(i); } SegTree t(n); for(int i = 1;i<=m;i++){ int l,r,k; cin >> l >> r >> k; ans[i] = t.get(l,r).val <= k; } for(int i = 1;i<=m;i++){ cout << ans[i] << '\n'; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef Local freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t=1; //cin>>t; while(t--){ solve(); } #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#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...