fork download
copy 
  1. // O(n*log(n)) megoldás
  2. // Legyen F(m)=|{i | a[i]>=c és i<=m}|, azaz c-nél nem kisebb tagok száma az első m tag között
  3. // Belátható, hogy (a[k],..,a[m]) pontosan akkor értékes, ha F(m)-F(k-1)>=(m-k+1)/2 ( és k<=m )
  4. // Legyen G(m)=2*F(m)-m
  5. // Kell: G(m)-G(k-1)>=0, azaz G(k-1)<=G(m) ( és persze k<=m )
  6. // Legyen H(m)=G(m)+n, ekkor 0<=H(m)<=2*n
  7.  
  8. #include <iostream>
  9. #include <new>
  10.  
  11. using namespace std;
  12.  
  13. int main(void){
  14.  
  15.   int **tree,pow2,depth,i,n,c,a,d,count,h,size,pos,pos2;
  16.   long long int answer;
  17.  
  18.   cin>>n>>c;  
  19.  
  20.   for(pow2=1,depth=0;pow2<2*n+1;pow2<<=1,depth++);
  21.  
  22.   tree=new int*[depth+1];
  23.   for(d=0;d<=depth;d++){
  24.     size=1+((2*n+1)>>d);
  25.     tree[d]=new int[size];
  26.     for(i=0;i<size;i++)tree[d][i]=0;
  27.   }
  28.  
  29.   answer=0;
  30.   count=0;
  31.   for(i=1;i<=n;i++){
  32.       cin>>a;
  33.  
  34.       count+=(a>=c);
  35.       h=2*count-i+n;
  36.       pos=-1;
  37.       pow2=1<<depth;
  38.       for(d=depth;d>=0;d--){
  39. 	      pos2=pos+pow2;
  40. 	      if(pos2<=h)pos=pos2,answer+=tree[d][pos>>d];
  41.           pow2>>=1;
  42.       }
  43.       answer+=(count>=(i+1)/2); // egész sorozat eddig értékes-e
  44.       for(d=0;d<=depth;d++)tree[d][h>>d]++;
  45.   }
  46.   cout<<answer<<endl;
  47.  
  48.   return 0;
  49. }
  50.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
4 6
10 5 6 2
stdout
copy 
7
https://ideone.com/ktBxy7
language:
C++ (gcc 8.3)
created:
10 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!