Submission #425316

#	Time	Username	Problem	Language	Result	Execution time	Memory
425316		dreezy	Quality Of Living (IOI10_quality)	C++17	40 / 100	5062 ms	3652 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

set<int> active;

int getmedian(){
	int cnt = 0;
	int median = -1;
	for(int a : active){
		if(cnt == active.size() / 2){
			median = a;
			break;
		}
		cnt++;
	}
	return median;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	active.clear();
	for(int top = 0; top < H; top ++){
		for(int left = 0; left < W; left++ ){
			active.insert(Q[top][left]);
		}
	}
	int ans = getmedian();
	for(int top = 0; top <= R - H; top++){
		
		//cout << top <<":\n";
		//if top % 2 === 0, we go from left to right
		
		if(top % 2 == 0){
			
			if(top > 0){
				for(int left = 0; left < W; left++ ){
					active.erase(Q[top - 1][left]);
					active.insert(Q[top + H - 1][left]);
				}
				ans = min(ans, getmedian());
			}
			for(int left = 1; left <=C - W;left++){
			//iterate left boundary of rectangle
				//cout << left << "->";
				for(int t = top; t < top + H; t++){
					active.erase(Q[t][left - 1]);
					active.insert(Q[t][left + W - 1]);
				}
				ans = min(ans, getmedian());
			}
		}
		else{
			if(top > 0){
				for(int right =  C - 1; right >= C - W; right-- ){
					active.erase(Q[top - 1][right]);
					active.insert(Q[top + H - 1][right]);
				}
				ans = min(ans, getmedian());
			}
			//we go from right to left
			for(int right = C  - 2; right >=W - 1; right--){
				//cout << right <<"->";
			//iterate left boundary of rectangle
				for(int t = top; t < top + H; t++){
					active.erase(Q[t][right + 1]);
					active.insert(Q[t][right - W +1]);
				}
				ans = min(ans, getmedian());
			}
		}
	
	//cout << endl;
	}
	
	return ans;
}

/***********/

Compilation message (stderr)

quality.cpp: In function 'int getmedian()':
quality.cpp:11:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   if(cnt == active.size() / 2){
      |      ~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20