Submission #1091897

#TimeUsernameProblemLanguageResultExecution timeMemory
1091897ihneHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
1086 ms137252 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pii pair<int,int> #define pb push_back const int mn=1e6+5; const int mod=1e9+7; int st[4*mn]; int a[mn]; struct query{ int l,k,id; }; vector<query> q[mn]; void update(int id,int l,int r,int pos,int val){ if (l>pos||r<pos) return; if (l==r){ st[id]=val; return; } int mid=l+r>>1; update(id<<1,l,mid,pos,val); update(id<<1|1,mid+1,r,pos,val); st[id]=max(st[id<<1],st[id<<1|1]); } int get(int id,int l,int r,int u,int v){ if (l>v||r<u) return -1e9; if (l>=u&&r<=v) return st[id]; int mid=l+r>>1; return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v)); } int ans[mn]; signed main(){ //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); int n,m; cin>>n>>m; for (int i=1;i<=n;i++){ cin>>a[i]; } memset(st,-0x3f,sizeof(st)); for (int i=1;i<=m;i++){ int l,r,k; cin>>l>>r>>k; q[r].pb({l,k,i}); } stack<pii> s; for (int i=1;i<=n;i++){ while (!s.empty()&&s.top().fi<a[i]) s.pop(); if (!s.empty()&&a[i]!=s.top().fi) update(1,1,n,i,a[i]+s.top().fi); s.push({a[i],i}); for (query x:q[i]) ans[x.id]=(get(1,1,n,x.l,i)<=x.k); } for (int i=1;i<=m;i++) cout<<ans[i]<<"\n"; }

Compilation message (stderr)

sortbooks.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:22:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |  int mid=l+r>>1;
      |          ~^~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid=l+r>>1;
      |          ~^~
#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...