Submission #1097614

#TimeUsernameProblemLanguageResultExecution timeMemory
10976140pt1mus23Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
666 ms116584 KiB
#include <bits/stdc++.h> using namespace std; #define int 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){ for(++node;node>0;node-=(node & -node)){ T[node]=max(T[node],v); } } int qry(int node){ int mx=0; for(++node;node<=sze; node +=(node & -node)){ mx=max(mx,T[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...