Advertisement
Guest User

Untitled

a guest
Aug 25th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.14 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define N 1000006
  3. #define INF 200005
  4. #define pb push_back
  5. #define st first
  6. #define nd second
  7. using namespace std;
  8. typedef long long ll;
  9. ll t, w, n, rmq[20][N], i, j, lg[N], l, r, ans[N];
  10. void fast()
  11. {
  12. ios_base::sync_with_stdio(false);
  13. cin.tie();
  14. }
  15.  
  16. int main()
  17. {
  18. fast();
  19. cin>>t>>w;
  20. for(i=2;i<=n;i++)
  21. lg[i]=lg[i/2]+1;
  22. while(t)
  23. {
  24. t--;
  25. cin>>n;
  26. for(i=1;i<=n;i++)
  27. cin>>rmq[0][i];
  28. for(i=1;i<=lg[n];i++)
  29. for(j=1;j<=n-(1<<(i-1))+1;j++)
  30. rmq[i][j]=max(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
  31. for(j=1;j<=w;j++)
  32. {
  33. l=max((ll)1,j-(w-n));
  34. r=min(n,j);
  35. //cout<<t<<' '<<j<<' '<<l<<' '<<r<<'\n';
  36. if(l<=r)
  37. {
  38. ll cand=max(rmq[lg[r-l]][l],rmq[lg[r-l]][r-(1<<lg[r-l])+1]);
  39. if(cand<0&&(j<w-n+1||j>n));
  40. else ans[j]+=cand;
  41. }
  42. }
  43. /**for(i=1;i<=w;i++)
  44. cout<<ans[i]<<' ';
  45. cout<<'\n';*/
  46. }
  47. for(i=1;i<=w;i++)
  48. cout<<ans[i]<<' ';
  49. return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement