JacobianDet

Untitled

Oct 26th, 2018
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define MV 1000005
  4. #define LMV 25
  5.  
  6. using namespace std;
  7.  
  8. int arr[MV];
  9. int SB[MV][LMV];
  10.  
  11. class ST
  12. {
  13. public: void build(int n);
  14. int query(int qs, int qd);
  15. };
  16.  
  17. void ST::build(int n)
  18. {
  19. for(int i=1;i<=n;i++)
  20. SB[i][0] = arr[i];
  21. for(int j=1;(1<<j)<=n;j++)
  22. {
  23. for(int i=1;i<=n;i++)
  24. {
  25. if(i + (1<<(j-1)) <= n)
  26. SB[i][j] = max(SB[i][j-1], SB[i+(1<<(j-1))][j-1]);
  27. }
  28. }
  29. return;
  30. }
  31.  
  32. int ST::query(int qs, int qd)
  33. {
  34. int lx = 0;
  35. for(lx=0;(1<<lx)<=(qd-qs+1);lx++);
  36. lx--;
  37. int mx = max(SB[qs][lx], SB[qd-(1<<lx)+1][lx]);
  38. return mx;
  39. }
  40.  
  41. int main(void)
  42. {
  43. std::ios_base::sync_with_stdio(false);
  44. std::cin.tie(NULL);
  45. std::cout.tie(NULL);
  46. int T;
  47. cin>>T;
  48. while(T--)
  49. {
  50. int n,k;
  51. cin>>n>>k;
  52. for(int i=1;i<=n;i++)
  53. cin>>arr[i];
  54. int ans = 0;
  55. vector<int> V;
  56. int li = 0;
  57. for(int i=1;i<=n;i++)
  58. {
  59. if(arr[i] > k)
  60. {
  61. if((int)V.size() > 0)
  62. {
  63. if(li != arr[i])
  64. {
  65. V.pb(i);
  66. li = arr[i];
  67. }
  68. }
  69. else
  70. {
  71. V.pb(i);
  72. li = arr[i];
  73. }
  74. }
  75. }
  76. ST Z;
  77. Z.build(n);
  78. for(int i=0,j=(int)V.size();i<j;i++)
  79. {
  80. if(!i)
  81. {
  82. int zx = Z.query(1, V[i]);
  83. if(k < zx)
  84. ans = max(ans, V[i]);
  85. }
  86. else if(i == 1)
  87. {
  88. int zx = Z.query(1, V[i] - 1);
  89. if(k < zx)
  90. ans = max(ans, V[i] - 1);
  91. }
  92. else
  93. {
  94. int zx = Z.query(V[i-2] + 1, V[i] - 1);
  95. if(k < zx)
  96. ans = max(ans, V[i] - V[i-2] - 1);
  97. }
  98. }
  99. if(V.size() >= 2)
  100. {
  101. int t = (int)V.size();
  102. int zx = Z.query(V[t-2] + 1, n);
  103. if(k < zx)
  104. ans = max(ans, n - V[t-2]);
  105. }
  106. std::sort(arr+1, arr+n+1);
  107. int mx1 = 0, mx2 = 0;
  108. for(int i=n;i>=1;i--)
  109. {
  110. if(arr[i] >= mx1)
  111. mx1 = arr[i];
  112. else if((mx1 > arr[i]) && (arr[i] >= mx2))
  113. {
  114. mx2 = arr[i];
  115. break;
  116. }
  117. }
  118. if((k < mx1) && (k >= mx2))
  119. ans = n;
  120. cout<<ans<<"\n";
  121. }
  122. return 0;
  123. }
Add Comment
Please, Sign In to add comment