Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define MV 1000005
- #define LMV 25
- using namespace std;
- int arr[MV];
- int SB[MV][LMV];
- class ST
- {
- public: void build(int n);
- int query(int qs, int qd);
- };
- void ST::build(int n)
- {
- for(int i=1;i<=n;i++)
- SB[i][0] = arr[i];
- for(int j=1;(1<<j)<=n;j++)
- {
- for(int i=1;i<=n;i++)
- {
- if(i + (1<<(j-1)) <= n)
- SB[i][j] = max(SB[i][j-1], SB[i+(1<<(j-1))][j-1]);
- }
- }
- return;
- }
- int ST::query(int qs, int qd)
- {
- int lx = 0;
- for(lx=0;(1<<lx)<=(qd-qs+1);lx++);
- lx--;
- int mx = max(SB[qs][lx], SB[qd-(1<<lx)+1][lx]);
- return mx;
- }
- int main(void)
- {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(NULL);
- std::cout.tie(NULL);
- int T;
- cin>>T;
- while(T--)
- {
- int n,k;
- cin>>n>>k;
- for(int i=1;i<=n;i++)
- cin>>arr[i];
- int ans = 0;
- vector<int> V;
- int li = 0;
- for(int i=1;i<=n;i++)
- {
- if(arr[i] > k)
- {
- if((int)V.size() > 0)
- {
- if(li != arr[i])
- {
- V.pb(i);
- li = arr[i];
- }
- }
- else
- {
- V.pb(i);
- li = arr[i];
- }
- }
- }
- ST Z;
- Z.build(n);
- for(int i=0,j=(int)V.size();i<j;i++)
- {
- if(!i)
- {
- int zx = Z.query(1, V[i]);
- if(k < zx)
- ans = max(ans, V[i]);
- }
- else if(i == 1)
- {
- int zx = Z.query(1, V[i] - 1);
- if(k < zx)
- ans = max(ans, V[i] - 1);
- }
- else
- {
- int zx = Z.query(V[i-2] + 1, V[i] - 1);
- if(k < zx)
- ans = max(ans, V[i] - V[i-2] - 1);
- }
- }
- if(V.size() >= 2)
- {
- int t = (int)V.size();
- int zx = Z.query(V[t-2] + 1, n);
- if(k < zx)
- ans = max(ans, n - V[t-2]);
- }
- std::sort(arr+1, arr+n+1);
- int mx1 = 0, mx2 = 0;
- for(int i=n;i>=1;i--)
- {
- if(arr[i] >= mx1)
- mx1 = arr[i];
- else if((mx1 > arr[i]) && (arr[i] >= mx2))
- {
- mx2 = arr[i];
- break;
- }
- }
- if((k < mx1) && (k >= mx2))
- ans = n;
- cout<<ans<<"\n";
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment