제출 #105918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105918		tincamatei	쌀 창고 (IOI11_ricehub)	C++14	100 / 100	53 ms	6544 KiB

ricehub

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

using namespace std;

const int MAX_N = 100;

struct MedianStructure {
	set<pair<int, int> > data;
	set<pair<int, int> >::iterator median;
	long long sumdists;
	

	MedianStructure() {
		sumdists = 0LL;
		median = data.end();
	}
	
	void moveMedian(int dir) {
		sumdists -= dir * median->first;
		
		if(dir == 1)
			median++;
		else
			median--;

		sumdists -= dir * median->first;
	}

	void insert(int val, int poz) {
		pair<int, int> x = make_pair(val, poz);

		data.insert(x);
		if(data.size() == 1)
			median = data.begin();
		else if(x < *median) {
			sumdists -= val;
			if(data.size() % 2 == 0) moveMedian(-1);
		} else {
			sumdists += val;
			if(data.size() % 2 == 1) moveMedian(+1);
		}
	}

	void erase(int val, int poz) {
		pair<int, int> x = make_pair(val, poz);
		
		if(x < *median) {
			sumdists += val;
			data.erase(x);
			if(data.size() % 2 == 1) moveMedian(1);
		} else if(x > *median) {
			sumdists -= val;
			if(data.size() % 2 == 1) moveMedian(-1);
			data.erase(x);
		} else if(data.size() % 2 == 0) {
			moveMedian(1);
			data.erase(x);
			sumdists += val;
		} else {
			moveMedian(-1);
			data.erase(x);
			sumdists -= val;
		}
	}

	long long getmediansum() {
		return sumdists - median->first * (1 - data.size() % 2);
	}
};

int besthub(int R, int L, int X[], long long B) {
	int l;
	int rez = 1;
	
	MedianStructure *med = new MedianStructure();

	// X[l...r] works
	l = 0;
	for(int r = 0; r < R; ++r) {
		med->insert(X[r], r);

		while(l < r && med->getmediansum() > B) {
			med->erase(X[l], l);
			l++;
		}

		rez = max(rez, r - l + 1);
	}

	return rez;
}

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