fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<vector>
  6. #define lli long long int
  7. using namespace std;
  8. lli arr[1000008];
  9. struct node
  10. {
  11.   lli val;
  12.   lli index;
  13. };
  14. struct node tail[1000008];
  15. int CeilIndex(lli l, lli r, lli key) {
  16.     int m;
  17.  
  18.     while( r - l > 1 ) {
  19.         m = l + (r - l)/2;
  20.         (tail[m].val >= key ? r : l) = m; // ternary expression returns an l-value
  21.     }
  22.  
  23.     return r;
  24. }
  25. lli condition(lli i,lli len)
  26. {
  27.    /*printf("\n%lld - %lld<= %lld-%lld\n",
  28.           i,tail[len-1].index,arr[i],tail[len-1].val
  29.           );*/
  30.    if(i-tail[len-1].index<=arr[i]-tail[len-1].val)
  31.     return 1;
  32.    return 0;
  33. }
  34. lli fun(lli n)
  35. {
  36.   /*printf("\n----------------------------\n");
  37.      for(lli i=0;i<n;i++)
  38.      {
  39.        printf("%lld ",tail[i].val);
  40.      }
  41.      printf("\n----------------------------\n");*/
  42. }
  43. lli lcs(lli n)
  44. {
  45.   for(lli i=0;i<n;i++)
  46.     tail[i].val=-1;
  47.  // fun(n);
  48.   tail[0].val=arr[0];
  49.   tail[0].index=0;
  50.   lli len=1;
  51.   for(lli i=1;i<n;i++)
  52.   {
  53.      if(arr[i]<tail[0].val && condition(i,len))
  54.      {
  55.        //printf("Entering 1\n");
  56.        tail[0].val=arr[i];
  57.        tail[0].index=i;
  58.      }
  59.      else if(arr[i]>tail[len-1].val && condition(i,len))
  60.      {
  61.       //   printf("Entering 2\n");
  62.          tail[len].val=arr[i];
  63.          tail[len].index=i;
  64.          len++;
  65.      }
  66.      else
  67.      {
  68.  
  69.     //    printf("Entering 3 && #%lld\n",condition(i,len));
  70.         lli z=CeilIndex(-1, len-1, arr[i]);
  71.         if(condition(i,z+1)==1)
  72.         {
  73.           tail[z].val=arr[i];
  74.           tail[z].index=i;
  75.         }
  76.      }
  77.     /* printf("\n----------------------------\n");
  78.      for(lli i=0;i<n;i++)
  79.      {
  80.        printf("%lld ",tail[i].val);
  81.      }
  82.      printf("\n----------------------------\n");*/
  83.   }
  84.   return n-len;
  85. }
  86. int main()
  87. {
  88.   lli n;
  89.   scanf("%lld",&n);
  90.   for(lli i=0;i<n;i++)
  91.   {
  92.     scanf("%lld",&arr[i]);
  93.   }
  94.   lli ans=lcs(n);
  95.    /*printf("\nfinalfinal----------------------------\n");
  96.      for(lli i=0;i<n;i++)
  97.      {
  98.        printf("%lld ",tail[i].val);
  99.      }
  100.      printf("\n");
  101.      for(lli i=0;i<n;i++)
  102.      {
  103.        printf("%lld ",tail[i].index);
  104.      }
  105.      printf("\n----------------------------\n");*/
  106.  
  107.   printf("%lld\n",ans);
  108. }
  109.  
Time limit exceeded #stdin #stdout 5s 26536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ww58P6
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!