# C. Median Splits [문제 링크](https://codeforces.com/contest/2103/problem/C) ## Problem Statement The median of an array $b_1, b_2, \ldots, b_m$, written as $\operatorname{med}(b_1, b_2, \ldots, b_m)$, is the $\left\lceil \frac{m}{2} \right\rceil$-th smallest element of array $b$. You are given an array of integers $a_1, a_2, \ldots, a_n$ and an integer $k$. You need to determine whether there exists a pair of indices $1 \le l < r < n$ such that: $$ \operatorname{med}\big(\operatorname{med}(a_1, a_2, \ldots, a_l),\ \operatorname{med}(a_{l+1}, a_{l+2}, \ldots, a_r),\ \operatorname{med}(a_{r+1}, a_{r+2}, \ldots, a_n)\big) \le k. $$ In other words, determine whether it is possible to split the array into three contiguous subarrays (†) such that the median of the three subarray medians is less than or equal to $k$. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains two integers $n$ and $k$ ($3 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$) — the length of the array $a$ and the constant $k$. The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each testcase, output `"YES"` if such a split exists, and `"NO"` otherwise. You can output the answer in any case (upper or lower). For example, the strings `"yEs"`, `"yes"`, `"Yes"`, and `"YES"` will be recognized as positive responses. ## Footnotes (∗) $\lceil x \rceil$ is the ceiling function which returns the least integer greater than or equal to $x$. (†) An array $x$ is a subarray of an array $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. ## 풀이 #### (앞에서부터 두 덩어리 / 뒤에서부터 두 덩어리 / 앞에서부터 한 덩어리, 뒤에서부터 한 덩어리) 그리디하게 이 세 가지 경우를 살펴보면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int n, k; int arr[200'000]; bool solve() { // 앞에 두덩이 int cnt=0, low=0, high=0; for(int i=0;i<n;i++) { if(arr[i]<=k) low++; else high++; if(low>0 && low>=high) { if(low>high && i+1<n && arr[i+1]>k) i++; cnt++; low=high=0; } } if(cnt>=2) return true; // 뒤에 두덩이 cnt=low=high=0; for(int i=n-1;i>=0;i--) { if(arr[i]<=k) low++; else high++; if(low>0 && low>=high) { if(low>high && i-1>=0 && arr[i-1]>k) i--; cnt++; low=high=0; } } if(cnt>=2) return true; // 앞 뒤 한덩이씩 cnt=low=high=0; int i=0; for(;i<n;i++) { if(arr[i]<=k) low++; else high++; if(low>0 && low>=high) { if(low>high && i+1<n && arr[i+1]>k) i++; cnt++; low=high=0; break; } } for(int j=n-1;j>i;j--) { if(arr[j]<=k) low++; else high++; if(low>0 && low>=high) { cnt++; break; } } if(cnt>=2) return true; return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { cin >> n >> k; for(int i=0;i<n;i++) cin >> arr[i]; cout << (solve() ? "YES\n" : "NO\n"); } } ```