Submission #765895

#	Time	Username	Problem	Language	Result	Execution time	Memory
765895		NeroZein	Rice Hub (IOI11_ricehub)	C++17	100 / 100	337 ms	6496 KiB

ricehub

#include "ricehub.h"
#include "bits/stdc++.h"
using namespace std; 

long long sl, sh; 
multiset<int> lo, hi; 

void balance () {
  if (lo.size() > hi.size() + 1) {
    int top = *lo.rbegin();
    lo.erase(lo.find(top)); 
    hi.insert(top);
    sl -= top;
    sh += top; 
  } else if (hi.size() > lo.size()) {
    int top = *hi.begin();
    hi.erase(hi.find(top));
    lo.insert(top); 
    sh -= top; 
    sl += top;
  }
}

void ins(int x) {
  if (lo.empty() || x <= *lo.rbegin()) {
    sl += x;     
    lo.insert(x); 
  } else {
    sh += x;
    hi.insert(x); 
  }
  balance(); 
}

void rem (int x) {
  if (x <= *lo.rbegin()) {
    lo.erase(lo.find(x)); 
    sl -= x; 
  } else {
    hi.erase(hi.find(x)); 
    sh -= x; 
  }
  balance(); 
}

long long getDis() {
  int med = *lo.rbegin();
  long long ret = 0;
  ret += (long long) med * lo.size() - sl;
  ret += sh - (long long) med * hi.size(); 
  return ret; 
}

void debug () {
  cout << "LO: ";
  for (int u : lo) cout << u << ' ';
  cout << '\n';
  cout << "HI: ";
  for (int u : hi) cout << u << ' ';
  cout << '\n';
  cout << "Med, Dis: " << *lo.rbegin() << ' ' << getDis() << '\n';
}

int besthub(int R, int L, int X[], long long B) {
  int l = 1, r = R; 
  while (l < r) {
    bool ok = false; 
    int mid = (l + r + 1) >> 1;
    for (int i = 0; i < mid; ++i) {
      ins(X[i]); 
    }
    if (getDis() <= B) {
      ok = true; 
    } 
    //debug();
    for (int i = mid; i < R; ++i) {
      rem(X[i - mid]);
      ins(X[i]); 
      if (getDis() <= B) {
        ok = true; 
      } 
      //debug(); 
    }
    if (ok) {
      l = mid;
    } else {
      r = mid - 1; 
    }
    sl = 0, sh = 0; 
    lo.clear();
    hi.clear();
    cout << '\n'; 
  }
  return l; 
}

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