oj.uz

Submission #1009366

# Submission time Handle Problem Language Result Execution time Memory
1009366 2024-06-27T12:09:49 Z Mardonbekhazratov Rice Hub (IOI11_ricehub) C++17
0 / 100
 49 ms 1372 KB 
#include "ricehub.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;

multiset<int>lept,rigt;
ll s1,s2;

void fix(){
    int sz=lept.size()+rigt.size();
    while(lept.size()>(sz+1)/2){
        int x=*lept.rbegin();
        rigt.insert(x);
        lept.erase(lept.find(x));
        s1-=x;
        s2+=x;
    }
    while(rigt.size()>sz/2){
        int x=*rigt.begin();
        lept.insert(x);
        rigt.erase(rigt.find(x));
        s1+=x;
        s2-=x;
    }
}

void ins(int x){
    if(lept.empty()){
        lept.insert(x);
        s1+=x;
        return;
    }
    int mid=*lept.rbegin();
    if(x>mid) rigt.insert(x),s2+=x;
    else lept.insert(x),s1+=x;
    fix();
}

void erase(int x){
    int mid=*lept.rbegin();
    if(x>mid) rigt.erase(rigt.find(x)),s2-=x;
    else lept.erase(lept.find(x)),s1-=x;
    fix();
}

int besthub(int R, int L, int X[], long long B){
    int l=1,r=R+1;
    while(r-l>1){
        int mid=(l+r)/2;
        bool ok=false;
        for(int i=0;i<R;i++){
            ins(X[i]);
            if(i>=mid) erase(X[i-mid]);
            if(i>=mid-1){
                ll x=*lept.rbegin();
                ok=ok?ok:lept.size()*x-s1+s2-rigt.size()*x<=B;
            }
        }
        if(ok) l=mid;
        else r=mid;
    }
    return l;
}

Compilation message

ricehub.cpp: In function 'void fix()':
ricehub.cpp:11:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |     while(lept.size()>(sz+1)/2){
      |           ~~~~~~~~~~~^~~~~~~~~
ricehub.cpp:18:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     while(rigt.size()>sz/2){
      |           ~~~~~~~~~~~^~~~~
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:56:59: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   56 |                 ok=ok?ok:lept.size()*x-s1+s2-rigt.size()*x<=B;
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 444 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -