fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int T;
  10.     cin >> T;
  11.     while(T--){
  12.         int n;
  13.         ll k;
  14.         cin >> n >> k;
  15.         vector<ll> a(n+1), S(n+1,0);
  16.         for(int i=1;i<=n;i++){
  17.             cin >> a[i];
  18.             S[i] = S[i-1] + (a[i] <= k);
  19.         }
  20.  
  21.         // Prefix-good: P[i] = true if [1..i] has median ≤ k
  22.         vector<char> P(n+1, 0);
  23.         for(int i=1;i<=n;i++){
  24.             int m = i;
  25.             ll cnt = S[i];
  26.             // need cnt ≥ ceil(m/2)
  27.             if (2*cnt >= m + (m&1))
  28.                 P[i] = 1;
  29.         }
  30.         // Suffix-good: Q[i] = true if [i..n] has median ≤ k
  31.         // we'll use Q[r+1]
  32.         vector<char> Q(n+2, 0);
  33.         for(int i=n;i>=1;i--){
  34.             int m = n - i + 1;
  35.             ll cnt = S[n] - S[i-1];
  36.             if (2*cnt >= m + (m&1))
  37.                 Q[i] = 1;
  38.         }
  39.  
  40.         // Build D_even[i] = 2*S[i] - i
  41.         //       D_odd [i] = 2*S[i] - i - 1
  42.         vector<ll> De(n+1), Do(n+1);
  43.         for(int i=1;i<=n;i++){
  44.             De[i] = 2*S[i] - i;
  45.             Do[i] = 2*S[i] - i - 1;
  46.         }
  47.  
  48.         // Build suffix‐max for middle‐good checks, split by parity
  49.         //   for r in [i..n-1], parity = r%2
  50.         vector<array<ll,2>> sufMaxE(n+2, {LLONG_MIN,LLONG_MIN});
  51.         vector<array<ll,2>> sufMaxO(n+2, {LLONG_MIN,LLONG_MIN});
  52.         for(int i=n-1;i>=1;i--){
  53.             sufMaxE[i] = sufMaxE[i+1];
  54.             sufMaxO[i] = sufMaxO[i+1];
  55.             int p = i&1;
  56.             sufMaxE[i][p] = max(sufMaxE[i][p], De[i]);
  57.             sufMaxO[i][p] = max(sufMaxO[i][p], Do[i]);
  58.         }
  59.  
  60.         // Build prefix‐min for the other middle‐good check
  61.         vector<array<ll,2>> preMinE(n+1, {LLONG_MAX,LLONG_MAX});
  62.         vector<array<ll,2>> preMinO(n+1, {LLONG_MAX,LLONG_MAX});
  63.         for(int i=1;i<=n-1;i++){
  64.             preMinE[i] = preMinE[i-1];
  65.             preMinO[i] = preMinO[i-1];
  66.             int p = i&1;
  67.             preMinE[i][p] = min(preMinE[i][p], De[i]);
  68.             preMinO[i][p] = min(preMinO[i][p], Do[i]);
  69.         }
  70.  
  71.         bool ok = false;
  72.  
  73.         // Case 1: prefix & middle
  74.         //   find ℓ in [1..n-2] with P[ℓ]
  75.         //   and some r>ℓ with middle‐good:
  76.         //     either (r-ℓ even) & De[r] ≥ De[ℓ]
  77.         //          or (r-ℓ odd ) & Do[r] ≥ Do[ℓ]
  78.         for(int l=1;l<=n-2 && !ok;l++){
  79.             if(!P[l]) continue;
  80.             int p = l&1;
  81.             // even‐length mid: r%2==p
  82.             if(sufMaxE[l+1][p] >= De[l]){
  83.                 ok = true;
  84.                 break;
  85.             }
  86.             // odd‐length mid: r%2!=p
  87.             if(sufMaxO[l+1][p^1] >= Do[l]){
  88.                 ok = true;
  89.                 break;
  90.             }
  91.         }
  92.  
  93.         // Case 2: middle & suffix
  94.         //   find r in [2..n-1] with Q[r+1]
  95.         //   and some ℓ< r with middle‐good:
  96.         //     either (r-ℓ even) & De[r] ≥ De[ℓ]
  97.         //          or (r-ℓ odd ) & Do[r] ≥ Do[ℓ]
  98.         for(int r=2;r<=n-1 && !ok;r++){
  99.             if(!Q[r+1]) continue;
  100.             int p = r&1;
  101.             // even‐length mid: ℓ%2==p
  102.             if(preMinE[r-1][p] <= De[r]){
  103.                 ok = true;
  104.                 break;
  105.             }
  106.             // odd‐length mid: ℓ%2!=p
  107.             if(preMinO[r-1][p^1] <= Do[r]){
  108.                 ok = true;
  109.                 break;
  110.             }
  111.         }
  112.  
  113.         // Case 3: prefix & suffix
  114.         //   any ℓ<r with P[ℓ] and Q[r+1]
  115.         int seenP = 0;
  116.         for(int r=2;r<=n-1 && !ok;r++){
  117.             if(P[r-1]) seenP = 1;
  118.             if(seenP && Q[r+1]){
  119.                 ok = true;
  120.                 break;
  121.             }
  122.         }
  123.  
  124.         cout << (ok ? "YES\n" : "NO\n");
  125.     }
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6
3 2
3 2 1
3 1
3 2 1
6 3
8 5 3 1 6 4
8 7
10 7 12 16 3 15 6 11
6 8
7 11 12 4 9 17
3 500000000
1000 1000000000 1000
stdout
copy 
YES
NO
NO
YES
YES
YES
https://ideone.com/U3CqCI
language:
C++ (gcc 8.3)
created:
3 days 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!