from sys import stdin
input = stdin.readline
inp = lambda : list(map(int,input().split()))
class SortedList:
def __init__(self, iterable=[], _load=200):
values = sorted(iterable)
self._len = _len = len(values)
self._load = _load
self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
self._list_lens = [len(_list) for _list in _lists]
self._mins = [_list[0] for _list in _lists]
self._fen_tree = []
self._rebuild = True
def _fen_build(self):
self._fen_tree[:] = self._list_lens
_fen_tree = self._fen_tree
for i in range(len(_fen_tree)):
if i | i + 1 < len(_fen_tree):
_fen_tree[i | i + 1] += _fen_tree[i]
self._rebuild = False
def _fen_update(self, index, value):
if not self._rebuild:
_fen_tree = self._fen_tree
while index < len(_fen_tree):
_fen_tree[index] += value
index |= index + 1
def _fen_query(self, end):
if self._rebuild:
self._fen_build()
_fen_tree = self._fen_tree
x = 0
while end:
x += _fen_tree[end - 1]
end &= end - 1
return x
def _fen_findkth(self, k):
_list_lens = self._list_lens
if k < _list_lens[0]:
return 0, k
if k >= self._len - _list_lens[-1]:
return len(_list_lens) - 1, k + _list_lens[-1] - self._len
if self._rebuild:
self._fen_build()
_fen_tree = self._fen_tree
idx = -1
for d in reversed(range(len(_fen_tree).bit_length())):
right_idx = idx + (1 << d)
if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
idx = right_idx
k -= _fen_tree[idx]
return idx + 1, k
def _delete(self, pos, idx):
_lists = self._lists
_mins = self._mins
_list_lens = self._list_lens
self._len -= 1
self._fen_update(pos, -1)
del _lists[pos][idx]
_list_lens[pos] -= 1
if _list_lens[pos]:
_mins[pos] = _lists[pos][0]
else:
del _lists[pos]
del _list_lens[pos]
del _mins[pos]
self._rebuild = True
def _loc_left(self, value):
if not self._len:
return 0, 0
_lists = self._lists
_mins = self._mins
lo, pos = -1, len(_lists) - 1
while lo + 1 < pos:
mi = (lo + pos) >> 1
if value <= _mins[mi]:
pos = mi
else:
lo = mi
if pos and value <= _lists[pos - 1][-1]:
pos -= 1
_list = _lists[pos]
lo, idx = -1, len(_list)
while lo + 1 < idx:
mi = (lo + idx) >> 1
if value <= _list[mi]:
idx = mi
else:
lo = mi
return pos, idx
def _loc_right(self, value):
if not self._len:
return 0, 0
_lists = self._lists
_mins = self._mins
pos, hi = 0, len(_lists)
while pos + 1 < hi:
mi = (pos + hi) >> 1
if value < _mins[mi]:
hi = mi
else:
pos = mi
_list = _lists[pos]
lo, idx = -1, len(_list)
while lo + 1 < idx:
mi = (lo + idx) >> 1
if value < _list[mi]:
idx = mi
else:
lo = mi
return pos, idx
def add(self, value):
_load = self._load
_lists = self._lists
_mins = self._mins
_list_lens = self._list_lens
self._len += 1
if _lists:
pos, idx = self._loc_right(value)
self._fen_update(pos, 1)
_list = _lists[pos]
_list.insert(idx, value)
_list_lens[pos] += 1
_mins[pos] = _list[0]
if _load + _load < len(_list):
_lists.insert(pos + 1, _list[_load:])
_list_lens.insert(pos + 1, len(_list) - _load)
_mins.insert(pos + 1, _list[_load])
_list_lens[pos] = _load
del _list[_load:]
self._rebuild = True
else:
_lists.append([value])
_mins.append(value)
_list_lens.append(1)
self._rebuild = True
def discard(self, value):
_lists = self._lists
if _lists:
pos, idx = self._loc_right(value)
if idx and _lists[pos][idx - 1] == value:
self._delete(pos, idx - 1)
def remove(self, value):
_len = self._len
self.discard(value)
if _len == self._len:
raise ValueError('{0!r} not in list'.format(value))
def pop(self, index=-1):
pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
value = self._lists[pos][idx]
self._delete(pos, idx)
return value
def bisect_left(self, value):
pos, idx = self._loc_left(value)
return self._fen_query(pos) + idx
def bisect_right(self, value):
pos, idx = self._loc_right(value)
return self._fen_query(pos) + idx
def count(self, value):
return self.bisect_right(value) - self.bisect_left(value)
def __len__(self):
return self._len
def __getitem__(self, index):
pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
return self._lists[pos][idx]
def __delitem__(self, index):
pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
self._delete(pos, idx)
def __contains__(self, value):
_lists = self._lists
if _lists:
pos, idx = self._loc_left(value)
return idx < len(_lists[pos]) and _lists[pos][idx] == value
return False
def __iter__(self):
return (value for _list in self._lists for value in _list)
def __reversed__(self):
return (value for _list in reversed(self._lists) for value in reversed(_list))
def __repr__(self):
return 'SortedList({0})'.format(list(self))
class OrderedList(SortedList): def __init__(self, arg):
super().__init__(arg)
def rangeCountByValue(self, leftVal, rightVal): leftCummulative = self.bisect_left(leftVal)
rightCummulative = self.bisect_left(rightVal + 1)
return rightCummulative - leftCummulative
M = (10 ** 9)
def answer(a):
if(n == k):return M
b = a[:]
take = [[a[i] , i] for i in range(n)]
take.sort()
for i in range(k):
a[take[i][1]] = M
value = -float('inf')
for i in range(n - 1):
value = max(value , min(a[i] , a[i + 1]))
value = min(value , 2 * min(a))
ans = value
a = b[:]
s = SortedList([])
for i in range(n):
s.add(a[i])
for i in range(n):
s.remove(a[i])
v = -float('inf')
if(i - 1 >= 0):v = max(v , a[i - 1])
if(i + 1 < n):v = max(v , a[i + 1])
ans = max(ans , min(v , 2 * s[k - 1]))
s.add(a[i])
if(k == 1):return ans
a = b[:]
s = SortedList([])
for i in range(n):
s.add(a[i])
for i in range(1 , n):
s.remove(a[i])
s.remove(a[i - 1])
ans = max(ans , 2 * s[k - 2])
s.add(a[i])
s.add(a[i - 1])
return min(M , ans)
for T in range(int(input())):
n , k = inp()
a = inp()
print(answer(a))
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, k, a[100010], pre[100010], sub[100010];
bool check(int pos) {
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + (int)((a[i] << 1) < pos);
for (int i = n; i; --i)
sub[i] = sub[i + 1] + (int)((a[i] << 1) < pos);
int minx = 0x7fffffff;
for (int i = 1; i < n; i++)
minx = min(minx, pre[i - 1] + sub[i + 2] + (int)(a[i] < pos) + (int)(a[i + 1] < pos));;
return minx <= k;
}
signed main() {
scanf("%lld", &t);
while (t--) {
scanf("%lld%lld", &n, &k);
memset(pre, 0, sizeof(pre));
memset(sub, 0, sizeof(sub));
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
int l = 0, r = 1e9, ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
printf("%lld\n", ans);
}
return 0;
}53. Maximum Subarray | 1527A. And Then There Were K |
1689. Partitioning Into Minimum Number Of Deci-Binary Numbers | 318. Maximum Product of Word Lengths |
448. Find All Numbers Disappeared in an Array | 1155. Number of Dice Rolls With Target Sum |
415. Add Strings | 22. Generate Parentheses |
13. Roman to Integer | 2. Add Two Numbers |
515. Find Largest Value in Each Tree Row | 345. Reverse Vowels of a String |
628. Maximum Product of Three Numbers | 1526A - Mean Inequality |
1526B - I Hate 1111 | 1881. Maximum Value after Insertion |
237. Delete Node in a Linked List | 27. Remove Element |
39. Combination Sum | 378. Kth Smallest Element in a Sorted Matrix |
162. Find Peak Element | 1529A - Eshag Loves Big Arrays |
19. Remove Nth Node From End of List | 925. Long Pressed Name |
1051. Height Checker | 695. Max Area of Island |
402. Remove K Digits | 97. Interleaving String |
543. Diameter of Binary Tree | 124. Binary Tree Maximum Path Sum |