This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../datastructure/sparsetable.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,l; cin>>n>>l; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; auto f=[](int a,int b){return min(a,b);}; SparseTable<int> st(f); st.build(as); for(int i=0;i+l<=n;i++){ if(i) cout<<" "; cout<<st.query(i,i+l); } cout<<endl; return 0; }
#line 1 "test/aoj/DSL_3_D.sparsetable.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "datastructure/sparsetable.cpp" #line 3 "datastructure/sparsetable.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> struct SparseTable{ using F = function<T(T, T)>; vector< vector<T> > dat; vector<int> ht; const F f; SparseTable(F f):f(f){} void build(const vector<T> &v){ int n=v.size(),h=1; while((1<<h)<=n) h++; dat.assign(h,vector<T>(n)); ht.assign(n+1,0); for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1; for(int j=0;j<n;j++) dat[0][j]=v[j]; for(int i=1,p=1;i<h;i++,p<<=1) for(int j=0;j<n;j++) dat[i][j]=f(dat[i-1][j],dat[i-1][min(j+p,n-1)]); }; T query(int a,int b){ int l=b-a; return f(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/aoj/DSL_3_D.sparsetable.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,l; cin>>n>>l; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; auto f=[](int a,int b){return min(a,b);}; SparseTable<int> st(f); st.build(as); for(int i=0;i+l<=n;i++){ if(i) cout<<" "; cout<<st.query(i,i+l); } cout<<endl; return 0; }