fork(1) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.      long long t,k,ans,n,inc=0,dec=0;
  9.     cin>>t;
  10.     while(t--)
  11.     {
  12.         inc=0;dec=0;
  13.          cin>>n>>k;
  14.  
  15.         vector<long long > a(n) ,b(n,1),c(n,1);
  16.  
  17.         for(int i=0;i<n;i++)
  18.             cin>>a[i];
  19.  
  20.  
  21. //STEP1
  22.         for(int i=1;i<n;i++)
  23.         {
  24.             if(a[i-1]<a[i])
  25.                 {
  26.                     b[i]=b[i-1]+1;
  27.                     c[i]=1;
  28.                 }
  29.             else if(a[i-1]>a[i])
  30.                 {
  31.                     c[i]=c[i-1]+1;
  32.                     b[i]=1;
  33.                 }
  34.             else
  35.                 {
  36.                     b[i]=b[i-1]+1;
  37.                     c[i]=c[i-1]+1;
  38.                 }
  39.         }
  40.  
  41. //STEP 2 and STEP 3
  42.     vector<long long> l,p;
  43.     bool flag1=true,flag2=false;
  44.     inc=b[0];
  45.     dec=c[0];
  46.     for(int i=1;i<n;i++)
  47.     {
  48.         if(i<k)
  49.         {
  50.             inc=inc+b[i];
  51.             dec=dec+c[i];
  52.         }
  53.         if(b[i]==1)
  54.             {
  55.                 l.push_back(b[i-1]);
  56.  
  57.             }
  58.         if(c[i]==1)
  59.             {
  60.                 p.push_back(c[i-1]);
  61.             }
  62.         if(i==n-1)
  63.         {
  64.             l.push_back(b[i]);
  65.             p.push_back(c[i]);
  66.         }
  67.  
  68.     }
  69.  
  70. //STEP 4
  71.     ans=inc-dec;
  72.      int j=0,o=0,inc2,dec2;
  73.  
  74.     for(int i=k;i<n;i++)
  75.     {
  76.         inc+=b[i]-b[i-k];
  77.         dec+=c[i]-c[i-k];
  78.  
  79.         inc2=inc;
  80.                 if(b[i-k+1]==1)
  81.             j++;
  82.         if(b[i-k+1]!=1)
  83.         {
  84.             if(b[i]-b[i-k+1]+1==k)
  85.             {
  86.                     inc2-=b[i-k]*k;
  87.             }
  88.             else
  89.             {
  90.                     inc2-=(b[i-k])*(l[j]-b[i-k+1]+1);
  91.             }
  92.         }
  93.  
  94.         dec2=dec;
  95.  
  96.         if(c[i-k+1]==1)
  97.             o++;
  98.         if(c[i-k+1]!=1)
  99.         {
  100.             if(c[i]-c[i-k+1]+1==k )
  101.             {
  102.                     dec2-=(c[i-k])*(k);
  103.             }
  104.                 else
  105.                 {
  106.  
  107.                     dec2-=(c[i-k])*(p[o]-c[i-k+1]+1);
  108.                 }
  109.  
  110.         }
  111.         ans+=(inc2-dec2);
  112.     }
  113.     cout<<ans<<endl;
  114.     }
  115.     return 0;
  116. }
  117.  
  118.  
  119.  
Runtime error #stdin #stdout #stderr 0s 2820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/lilYp7
COEX06
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!