Submission #153691

#TimeUsernameProblemLanguageResultExecution timeMemory
153691semiautoHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
2869 ms262144 KiB
#include <bits/stdc++.h> using namespace std; int n,m,i,j,l,r,ans,N=1024*1024; int mas[1000001],val[1000001],tree[2048*1024]; pair <int,int> p[1000001][20]; vector <int> v[1000001]; inline int maxi(int a,int b) { if (a>b) return a; return b; } void dfs(int u) { int i; for (i=1;i<20;i++) if (p[p[u][i-1].first][i-1].first) p[u][i]={p[p[u][i-1].first][i-1].first,maxi(p[u][i-1].second,p[p[u][i-1].first][i-1].second)}; for (i=0;i<(v[u].size());i++) dfs(v[u][i]); } int solve(int x,int y,int p,int l,int r) { if (l>y || x>r) return 0; if (l>=x && r<=y) return tree[p]; return maxi(solve(x,y,2*p,l,(l+r)/2),solve(x,y,2*p+1,(l+r)/2+1,r)); } void build_tree(int p) { if (p>=N) { if ((p-N+1)<=n) tree[p]=mas[p-N+1]; return; } build_tree(2*p); build_tree(2*p+1); tree[p]=maxi(tree[2*p],tree[2*p+1]); } int main() { scanf("%d %d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&(mas[i])); build_tree(1); for (i=n;i>0;i--) { for (;r>0;r--) if (mas[val[r]]>=mas[i]) break; p[i][0].first=val[r]; if (val[r]>(i+1)) p[i][0].second=mas[i]+solve(i+1+N-1,val[r]-1+N-1,1,N,2*N-1); v[val[r]].push_back(i); val[++r]=i; } for (i=0;i<(v[0].size());i++) dfs(v[0][i]); for (mas[0]=1;mas[0]<=m;mas[0]++) { scanf("%d %d %d",&l,&r,&j); if (l==r) { printf("1\n"); continue; } ans=0; for (i=19;i>=0;i--) if (p[l][i].first && p[l][i].first<=r) { ans=maxi(ans,p[l][i].second); l=p[l][i].first; } if (r>l) ans=maxi(ans,mas[l]+solve(l+1+N-1,r+N-1,1,N,2*N-1)); if (ans>j) printf("0\n"); else printf("1\n"); } }

Compilation message (stderr)

sortbooks.cpp: In function 'void dfs(int)':
sortbooks.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[u].size());i++)
              ~^~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[0].size());i++)
              ~^~~~~~~~~~~~~~
sortbooks.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&(mas[i]));
         ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&l,&r,&j);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...