Submission #1220670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220670		moha1111	Rice Hub (IOI11_ricehub)	C++20	100 / 100	330 ms	5516 KiB

ricehub

//#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;

bool valid (int n , int k , int a[] , long long t)
{
    multiset<int> l , r;
    long long sum1 = 0 , sum2 = 0;
    for(int i = 0 ; i < n ; i++)
    {
        if(i >= k)
        {
            if(l.find(a[i - k]) != l.end())
            {
                l.erase(l.find(a[i - k]));
                sum1 -= a[i - k];
            }
            else
            {
                r.erase(r.find(a[i - k]));
                sum2 -= a[i - k];
            }
        }
        if(l.size() <= r.size())
        {
            l.insert(a[i]);
            sum1 += a[i];
        }
        else
        {
            r.insert(a[i]);
            sum2 += a[i];
        }
        
        if(l.size() > 0 && r.size() > 0 && *l.rbegin() > *r.begin())
        {
            sum1 += (*r.begin() - *l.rbegin());
            sum2 += (*l.rbegin() - *r.begin());
            l.insert(*r.begin());
            r.insert(*l.rbegin());
            r.erase(r.begin());
            l.erase(l.find(*l.rbegin()));            
        }
        if(i >= k - 1 && (l.size() * *l.rbegin() - sum1) + (sum2 - *l.rbegin() * r.size()) <= t)
                return 1;
    }
    return 0;
}

int besthub(int r , int l , int a[] , long long b)
{
    long long st = 1 , en = r;
    int ans = 1;
    while(st <= en)
    {
        long long mid = (st + en) / 2;
        if(valid(r , mid , a , b))
            st = mid + 1 , ans = mid;

        else
            en = mid - 1;
    }
    return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32