Submission #153646

#TimeUsernameProblemLanguageResultExecution timeMemory
153646semiautoHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
1266 ms262148 KiB
#include <bits/stdc++.h> using namespace std; int n,m,i,j,l,r,ans; int mas[1000001],par[1000001],val[1000001],ori[1000001],hey[3000001],pre[1000001][20]; pair <int,int> p[1000001][20]; vector <int> v[1000001]; 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,max(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 a,int b) { int c=ori[b-a+1]; return max(pre[a][c],pre[b-(1<<c)+1][c]); } int main() { for (i=1;i<20;i++) ori[(1<<i)]=i; for (i=1;i<1000001;i++) if (!ori[i]) ori[i]=ori[i-1]; cin>>n>>m; for (i=1;i<=n;i++) { cin>>mas[i]; pre[i][0]=mas[i]; } for (j=1;j<20;j++) for (i=1;(i+(1<<j)-1)<=n;i++) pre[i][j]=max(pre[i][j-1],pre[i+(1<<(j-1))][j-1]); for (i=n;i>0;i--) { for (;r>0;r--) if (mas[hey[r]]>=mas[i]) break; par[i]=hey[r]; v[hey[r]].push_back(i); hey[++r]=i; } for (i=1;i<=n;i++) if (par[i]>(i+1)) val[i]=mas[i]+solve(i+1,par[i]-1); for (i=1;i<=1000000;i++) p[i][0]={par[i],val[i]}; return 0; for (i=0;i<(v[0].size());i++) dfs(v[0][i]); while (cin>>l>>r>>m) { if (l==r) { cout<<"1"<<endl; continue; } ans=0; for (i=19;i>=0;i--) if (p[l][i].first && p[l][i].first<=r) { ans=max(ans,p[l][i].second); l=p[l][i].first; } if (r>l) ans=max(ans,mas[l]+solve(l+1,r)); if (ans>m) cout<<"0"<<endl; else cout<<"1"<<endl; } }

Compilation message (stderr)

sortbooks.cpp: In function 'void dfs(int)':
sortbooks.cpp:12: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:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<(v[0].size());i++)
              ~^~~~~~~~~~~~~~
#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...