# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1220517 | moha1111 | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <cstdio>
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define all(a) a.begin() , a.end()
const long long mod = 1000000007;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>indexed_multiset;
void usaco(string s)
{
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
void solve()
{
long long r , l , b;
cin >> r >> l;
int a[r];
for(int i = 0 ; i < r ; i++)
cin >> a[i];
cin >> b;
long long st = 1 , en = r , ans;
while(st <= en)
{
long long mid = (st + en) / 2;
indexed_multiset cur;
for(int i = 0 ; i < mid ; i++)
cur.insert(a[i]);
if(mid % 2 == 0)
{
if(*cur.find_by_order(mid / 2) <= b)
{
st = mid + 1 , ans = mid;
continue;
}
for(int i = mid ; i < r ; i++)
{
cur.insert(a[mid]);
cur.erase(cur.find(a[i - mid]));
if(*cur.find_by_order(mid / 2) <= b)
{
st = mid + 1 , ans = mid;
continue;
}
}
en = mid - 1;
}
else
{
if(*cur.find_by_order(mid / 2) + *cur.find_by_order(mid / 2 + 1)<= b * 2)
{
st = mid + 1 , ans = mid;
continue;
}
for(int i = mid ; i < r ; i++)
{
cur.insert(a[mid]);
cur.erase(cur.find(a[i - mid]));
if(*cur.find_by_order(mid / 2) + *cur.find_by_order(mid / 2 + 1)<= b * 2)
{
st = mid + 1 , ans = mid;
continue;
}
}
en = mid - 1;
}
}
cout << ans << '\n';
}
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
//usaco("lostcow");
int t = 1;
//cin >> t;
while(t--)
solve();
}