fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;   
  3. #define pi pair<int,int>
  4. #define lli long long int
  5.  
  6. int n,k;
  7. int a[1000005];
  8. int tree[4000005][2];
  9.  
  10. void buildTree(int l ,int r, int index)
  11.     {
  12.         if(l==r)
  13.         {
  14.            tree[index][0] = a[l];
  15.            tree[index][1] = INT_MIN;
  16.            return;
  17.         }
  18.         int mid = (l+r)/2;
  19.         buildTree(l,mid,2*index);
  20.         buildTree(mid+1,r,2*index+1);
  21.  
  22.         int b[4];
  23.         b[0]=tree[2*index][0];
  24.         b[1]=tree[2*index][1];
  25.         b[2]=tree[2*index+1][0];
  26.         b[3]=tree[2*index+1][1];
  27.         sort(b,b+4);
  28.  
  29.         tree[index][0] = b[3];
  30.         tree[index][1] = b[2];
  31.         return;
  32. }
  33.  
  34.  
  35.  
  36.     pi query(int l ,int r , int ql,int qr,int index)
  37.     {
  38.         if(ql>r || qr<l)
  39.         {
  40.             return make_pair(INT_MIN,INT_MIN);
  41.         }
  42.  
  43.         if(l >= ql && r<=qr)
  44.         {
  45.             return make_pair(tree[index][0],tree[index][1]);
  46.         }
  47.  
  48.  
  49.         int mid = (l+r)/2;
  50.         pi val1 = query(l,mid,ql,qr,2*index);
  51.         pi val2 = query(mid+1,r,ql,qr,2*index+1);
  52.  
  53.         int b[4];
  54.         b[0]=val1.first;
  55.         b[1]=val1.second;
  56.         b[2]=val2.first;
  57.         b[3]=val2.second;
  58.         sort(b,b+4);
  59.  
  60.         return make_pair(b[3],b[2]);
  61.     }
  62.  
  63.      bool check(int mid){
  64.          for(int i=0;i<=(n-mid);i++){
  65.              pi x = query(0,n-1,i,i+mid-1,1);
  66.              if(x.first == x.second){
  67.                  if(k < x.first){
  68.                      return 1;
  69.                  }
  70.              }else if(k < x.first && k>=x.second){
  71.                  return 1;
  72.              }
  73.          }
  74.          return 0;
  75.      }
  76.  
  77.     int main()
  78.     {
  79.         ios_base::sync_with_stdio(false);
  80.         cin.tie(NULL);
  81.         int t;
  82.         cin>>t;
  83.         while(t--){
  84.             cin>>n>>k;
  85.             for(int i=0;i<n;i++)
  86.             {
  87.                 cin>>a[i];
  88.             }
  89.             if(n==1){
  90.                 if(a[0] > k){
  91.                     cout<<"1\n";
  92.                 }else{
  93.                     cout<<"0\n";
  94.                 }
  95.                 continue;
  96.             }
  97.             for(int i=0;i<=(4*n);i++){
  98.                 tree[i][0]=INT_MIN;
  99.                 tree[i][1]=INT_MIN;
  100.             }
  101.             buildTree(0,n-1,1);
  102.             /*for(int i=1;i<=4*n;i++)
  103.             {
  104.                 cout<<tree[i][0]<<" "<<tree[i][1]<<"\n";
  105.             }
  106.             cout<<"\n";*/
  107.             int l=0,r=n,mid,ans=0;
  108.             while(l<=r){
  109.                 mid = (l+r)/2;
  110.                 //cout<<mid<<"\n";
  111.                 if(check(mid)){
  112.                     //cout<<mid<<"\n";
  113.                     ans = mid;
  114.                     l = mid + 1;
  115.                 }else{
  116.                     r = mid - 1;
  117.                 }
  118.             }
  119.             cout<<ans<<"\n";
  120.         }
  121.         return 0;
  122.     }
  123.  
  124.  
  125.  
Success #stdin #stdout 0s 50392KB
comments (?)
stdin
copy 
1
3 3
78 11 80
stdout
copy 
1
https://ideone.com/fFD7cM
language:
C++14 (gcc 8.3)
created:
5 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!