Submission #976441

#	Time	Username	Problem	Language	Result	Execution time	Memory
976441		LaviniaTornaghi	Quality Of Living (IOI10_quality)	C++14	60 / 100	5034 ms	35156 KiB

quality

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

void print(multiset<int> x){
	for(auto i:x) cout<<i<<" ";
	cout<<endl;
}

int A,B;

void addcolumn(vector<vector<int>> &q, multiset <int> &s, int c, int sq, int eq){
	assert(eq<=A);
	for(int i=sq;i<eq;i++) s.insert(q[i][c]);
}
void removecolumn(vector<vector<int>> &q,multiset <int> &s, int c, int sq, int eq){
	assert(eq<=A);
	for(int i=sq;i<eq;i++){
		s.erase(s.lower_bound(q[i][c]));
	}
}
void addrow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
	assert(eq<=B);
	for(int i=sq;i<eq;i++) s.insert(q[r][i]);
}
void removerow(vector<vector<int>> &q, multiset <int> &s, int r, int sq, int eq){
	assert(eq<=B);
	for(int i=sq;i<eq;i++){
		s.erase(s.lower_bound(q[r][i]));
	}
}
int getmed(multiset<int>&s){
	/*int l = *(s.begin()), r = *(s.rbegin());
	while(r-l>1){
		int m = (l+r)/2;
		if( (s.lower_bound(m) - s.begin()) >(s.size()/2)) m = r;
		else l = m;
	}
	return l;*/
	auto x = s.begin();
	advance(x,s.size()/2);
	return *x;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<vector<int>> q(R,vector<int>(C)); A=R, B=C;
	for(int i=0;i<R;i++)
		for(int j=0;j<C;j++)
			q[i][j]=Q[i][j];
	
	multiset<int> s;
	int ans = INT_MAX;
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++)
			s.insert(q[i][j]);
	for(int i=0;i<=R-H;i++){
		if(!(i%2)){
			for(int j=1;j<=C-W;j++){
				ans = min(ans, getmed(s));
				removecolumn(q,s,j-1,i,i+H);
				addcolumn(q,s,j+W-1,i,i+H);
			}
			ans = min(ans,getmed(s));
			removerow(q,s,i,C-W,C);
			if(i+H<R)addrow(q,s,i+H,C-W,C);
		}else{
			for(int j=C-W-1;j>=0;j--){
				ans = min(ans, getmed(s));
				removecolumn(q,s,j+W,i,i+H);
				addcolumn(q,s,j,i,i+H);
			}
			ans = min(ans,getmed(s));
			removerow(q,s,i,0,W);
			if(i+H<R) addrow(q,s,i+H,0,W);
		}
	}
	return ans;
}

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