Submission #1097613

#TimeUsernameProblemLanguageResultExecution timeMemory
10976130pt1mus23Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
643 ms105996 KiB
#include <bits/stdc++.h> using namespace std; #define int unsigned long long #define ins insert #define pb push_back #define putr(x) cout<<x<<endl;return; #define all(x) x.begin(),x.end() #define endl '\n' #define _ << " " << const int mod = 1e9+7, sze = 1e6 +23*2, inf = 1e9, L = 23 ; int T[sze+23]; void upd(int node,int v){ node++; while(node<=sze){ T[node]=max(T[node],v); node += (node & -node); } } int qry(int node){ int mx=0; node++; while(node>0){ mx=max(mx,T[node]); node -= (node & -node); } return mx; } void _0x0(){ int n,q; cin>>n>>q; vector<int> arr(n); vector<int> ans(q,0); for(int i=0;i<n;i++){ cin>>arr[i]; } vector< vector< pair< pair<int,int>, int> > > event(n+10); int idx=0; while(q--){ int l,r,k; cin>>l>>r>>k; --l;--r; event[r].pb( { {l,k}, idx++} ); } vector<int> lst; for(int i=0;i<n;i++){ while(!lst.empty() && arr[lst.back()]<=arr[i]){ lst.pop_back(); } if(!lst.empty()){ upd(lst.back(), arr[lst.back()] + arr[i]); } lst.pb(i); for(auto v:event[i]){ if(qry(v.first.first)<=v.first.second){ ans[v.second]=1; } } } for(auto v:ans)cout<<v<<endl; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; // cin>>tt; while(tt--){ _0x0(); } 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...