SHARE
TWEET

Untitled

a guest Sep 13th, 2017 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #define NMAX 10000
  3.  
  4. int i,imax,n,lh,lr,a[NMAX],h[NMAX],hr[NMAX],v[NMAX],aib[NMAX],d[NMAX],p[NMAX],r[NMAX];
  5.  
  6. void mergesort(int l,int r) {
  7.   int mid=l+(r-l)/2,i,j,k;
  8.   if(l<r) {
  9.     mergesort(l,mid);
  10.     mergesort(mid+1,r);
  11.     i=k=l;
  12.     j=mid+1;
  13.     while((i<=mid)&&(j<=r))
  14.      if(a[h[i]]<a[h[j]]) hr[k++]=h[i++];
  15.      else hr[k++]=h[j++];
  16.     if(i>mid)
  17.      while(j<=r) hr[k++]=h[j++];
  18.     else
  19.      while(i<=mid) hr[k++]=h[i++];
  20.     for(i=l;i<=r;i++) h[i]=hr[i];
  21.   }
  22. }
  23.  
  24. void vcalculate() {
  25.   int i,k=1;
  26.   for(i=1;i<=n;i++) h[i]=i;
  27.   mergesort(1,n);
  28.   v[h[1]]=1;
  29.   for(i=2;i<=n;i++)
  30.    if(a[h[i]]!=a[h[i-1]]) v[h[i]]=++k;
  31.    else v[h[i]]=k;
  32. }
  33.  
  34. // begin - AIB operations
  35. void update(int x,int ind) {
  36.   while(x<=n) {
  37.     if(d[ind]>d[aib[x]]) aib[x]=ind;
  38.     x+=x^(x-1)&x;
  39.   }
  40. }
  41.  
  42. int query(int x) {
  43.   int max=0;
  44.   while(x) {
  45.     if(d[aib[x]]>d[max]) max=aib[x];
  46.     x-=x^(x-1)&x;
  47.   }
  48.   return max;
  49. }
  50. // end - AIB operations
  51.  
  52. // begin - I/O operations
  53. void readfile() {
  54.   freopen("scmax.in","r",stdin);
  55.   scanf("%d",&n);
  56.   for(int i=1;i<=n;i++) scanf("%d",a+i);
  57.   fclose(stdin);
  58. }
  59.  
  60. void writefile() {
  61.   freopen("scmax.out","w",stdout);
  62.   printf("%d\n",lr);
  63.   for(int i=1;i<=lr;i++) printf("%d ",r[i]);
  64.   fclose(stdout);
  65. }
  66. // end - I/O operations
  67.  
  68. int main() {
  69.   readfile();
  70.   vcalculate();
  71.   d[0]=0;
  72.   for(i=1;i<=n;i++) {
  73.     p[i]=query(v[i]-1);
  74.     d[i]=d[p[i]]+1;
  75.     update(v[i],i);
  76.   }
  77.   imax=1;
  78.   for(i=2;i<=n;i++)
  79.    if(d[i]>d[imax]) imax=i;
  80.   lr=d[imax];
  81.   r[lr]=a[imax];
  82.   for(i=lr-1;i>0;i--) {
  83.     imax=p[imax];
  84.     r[i]=a[imax];
  85.   }
  86.   writefile();
  87.   return 0;
  88. }
RAW Paste Data
Top