# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1220528 | moha1111 | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include "ricehub.h"
#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;
int besthub(long long r, long long L, int a[], long long 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';
}