Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define N 1000006
- #define INF 200005
- #define pb push_back
- #define st first
- #define nd second
- using namespace std;
- typedef long long ll;
- ll t, w, n, rmq[20][N], i, j, lg[N], l, r, ans[N];
- void fast()
- {
- ios_base::sync_with_stdio(false);
- cin.tie();
- }
- int main()
- {
- fast();
- cin>>t>>w;
- for(i=2;i<=n;i++)
- lg[i]=lg[i/2]+1;
- while(t)
- {
- t--;
- cin>>n;
- for(i=1;i<=n;i++)
- cin>>rmq[0][i];
- for(i=1;i<=lg[n];i++)
- for(j=1;j<=n-(1<<(i-1))+1;j++)
- rmq[i][j]=max(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
- for(j=1;j<=w;j++)
- {
- l=max((ll)1,j-(w-n));
- r=min(n,j);
- //cout<<t<<' '<<j<<' '<<l<<' '<<r<<'\n';
- if(l<=r)
- {
- ll cand=max(rmq[lg[r-l]][l],rmq[lg[r-l]][r-(1<<lg[r-l])+1]);
- if(cand<0&&(j<w-n+1||j>n));
- else ans[j]+=cand;
- }
- }
- /**for(i=1;i<=w;i++)
- cout<<ans[i]<<' ';
- cout<<'\n';*/
- }
- for(i=1;i<=w;i++)
- cout<<ans[i]<<' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement