fork download
copy 
  1. /******************
  2.    TESTER CODE
  3.  
  4.     **OPTIMAL**
  5.  
  6. Problem- Count Nodes
  7. Tester- spj_29
  8. Complexity- nlog^2(n) ( can be improved to nlognlog(logn) )
  9.  
  10. *******************/
  11. #include <bits/stdc++.h>
  12.  
  13. using namespace std;
  14.  
  15. #define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  16. #define fileio freopen("input1.txt", "r", stdin),freopen("output1.txt", "w", stdout)
  17. #define ll int
  18. #define FF first
  19. #define SS second
  20. #define mp make_pair
  21. #define pb push_back
  22. #define pii pair<int,int>
  23. #define pll pair<long long int,long long int>
  24. #define sd(x) scanf("%d",&x)
  25. #define slld(x) scanf("%lld",&x)
  26. #define pd(x) printf("%d\n",x)
  27. #define plld(x) printf("%lld\n",x)
  28. #define pss printf
  29. #define MOD 1000000007
  30. #define INF 1e18
  31. #define eps 0.00001
  32. #define endl '\n'
  33. #define debug(n1) cout<<n1<<endl
  34. ll n,t;
  35. ll dp[2][31][50005];
  36. ll at[31][50005];
  37. ll m[50005];
  38. ll ans[31];
  39. ll cnt=0;
  40. void build(ll l,ll r,ll d)
  41. {
  42.     at[d][r]=l;
  43.     if(m[r]==0)m[r]=d;
  44.     if(l==r)return;
  45.     ll mid=(l+r)>>1;
  46.     build(l,mid,d+1);
  47.     build(mid+1,r,d+1);
  48. }
  49. void clear()
  50. {
  51.     cnt=0;
  52.     memset(m,0,sizeof m);
  53.     memset(ans,0,sizeof ans);
  54.     memset(dp,0,sizeof dp);
  55.     memset(at,0,sizeof at);
  56. }
  57. int main() {
  58. sd(t);
  59. while(t--)
  60. {
  61.     clear();
  62.     sd(n);
  63.     build(1,n,1);
  64.     for(int i=0;i<31;i++)
  65.         dp[0][i][0]=1;
  66.     for(int j=1;j<=n;j++)
  67.         dp[0][30][j]=1;
  68.     for(int i=1;i<31;i++)
  69.     {
  70.         for(int j=0;j<=n;j++)
  71.         {
  72.             for(int h=0;h<31;h++)
  73.                 dp[i%2][h][j]=0;
  74.             for(int h=m[j];at[h][j]!=0;h++)
  75.             {
  76.                 dp[i%2][h][j]=dp[1-(i%2)][30][at[h][j]-1];
  77.                 if(h!=m[j])
  78.                     dp[i%2][h][j]-=dp[1-(i%2)][h][at[h][j]-1];
  79.             }
  80.             for(int h=1;h<31;h++)
  81.                 dp[i%2][h][j]+=dp[i%2][h-1][j];
  82.             ans[i]+=dp[(i%2)][30][j];
  83.         }
  84.         if(ans[i])cnt++;
  85.         else break;
  86.     }
  87.     pd(cnt);    
  88.     for(int i=1;i<=cnt;i++)
  89.         pss("%d ",ans[i]);
  90.     pss("\n");
  91. }
  92.     return 0;
  93.            }
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/m3LQUq
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!