Submission #520838

#	Time	Username	Problem	Language	Result	Execution time	Memory
520838		Alex_tz307	Rice Hub (IOI11_ricehub)	C++17	100 / 100	37 ms	6424 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"

using namespace std;

int median = -1;
multiset<int> low, big;
int64_t sum_low, sum_big;

void fix() {
  int m = (low.size() + big.size()) >> 1;
  if ((int)low.size() < m) {
    low.emplace(median);
    sum_low += median;
    median = *big.begin();
    big.erase(big.begin());
    sum_big -= median;
  }
  if ((int)low.size() > m) {
    big.emplace(median);
    sum_big += median;
    median = *--low.end();
    low.erase(--low.end());
    sum_low -= median;
  }
}

void add(int x) {
  if (median == -1) {
    median = x;
    return;
  }
  if (x < median) {
    low.emplace(x);
    sum_low += x;
  } else {
    big.emplace(x);
    sum_big += x;
  }
  fix();
}

void rem(int x) {
  if (x == median) {
    median = *big.begin();
    big.erase(big.begin());
    sum_big -= median;
  } else {
    if (x < median) {
      low.erase(low.find(x));
      sum_low -= x;
    } else {
      big.erase(big.find(x));
      sum_big -= x;
    }
  }
  fix();
}

int64_t cost() {
  return (int64_t)low.size() * median - sum_low + sum_big - (int64_t)big.size() * median;
}

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

int besthub(int R, int L, int X[], long long B) {
  int ans = 1, l = 0;
  for (int r = 0; r < R; ++r) {
    add(X[r]);
    while (B < cost()) {
      rem(X[l]);
      l += 1;
    }
    maxSelf(ans, r - l + 1);
  }
  return ans;
}

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