Submission #740023

#	Time	Username	Problem	Language	Result	Execution time	Memory
740023		fractlpaca	Quality Of Living (IOI10_quality)	C++17	60 / 100	5041 ms	23784 KiB

quality

#include "quality.h"

#include <vector>
#include <algorithm>
//#include <iostream>

#define v vector

using namespace std;

// Subtask 1 & 2: Brute Force

// int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
// 	int median = R*C;
// 	for (int i=0; i<R-H+1; i++) {
// 		for (int j=0; j<C-W+1; j++) {
// 			v<int> blocks;
// 			for (int s=i; s<i+H; s++) {
// 				for (int t=j; t<j+W; t++) {
// 					blocks.push_back(Q[s][t]);
// 				}
// 			}
// 			sort(blocks.begin(), blocks.end());
// 			median = min(median, blocks[(H*W)/2]);
// 		}
// 	}
// 	return median;
// }




// Subtask 3: seg tree

v<int> tree;

int query(int pos, int l, int r, int index) {
	if (l==r) return l;
	int mid = (l+r)/2;
	if (tree[index*2] >= pos) {
		return query(pos, l, mid, index*2);
	} else {
		return query(pos - tree[index*2], mid+1, r, index*2+1);
	}
}

void update(int pos, int val, int l, int r, int index) {
	if (l==r) {
		tree[index] = val;
		return;
	}
	int mid = (l+r)/2;
	if (pos<=mid) {
		update(pos, val, l, mid, index*2);
	} else {
		update(pos, val, mid+1, r, index*2+1);
	}
	tree[index] = tree[index*2] + tree[index*2+1];
}


int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	//cerr<<R<<" "<<C<<" "<<H<<" "<<W<<" "<<(H*W)/2<<endl;
	int n=R*C;
	int pos = (H*W)/2 + 1;

	tree = v<int> (4*(n+1), 0);
	
	int median = R*C - (H*W)/2;
	for (int i=0; i<R-H+1; i++) {
		// Setup
		for (int s=i; s<i+H; s++) {
			for (int t=0; t<W; t++) {
				update(Q[s][t], 1, 1, n, 1);
			}
		}
		//cerr<<"("<<i<<", 0) "<<query(pos, 1, n, 1)<<endl;
		median = min(median, query(pos, 1, n, 1));
		// Slide window
		for (int j=1; j<C-W+1; j++) {
			for (int s=i; s<i+H; s++) {
				update(Q[s][j-1], 0, 1, n, 1);
				update(Q[s][j+W-1], 1, 1, n, 1);
				//cerr<<"-"<<Q[s][j-1]<<" +"<<Q[s][j+W-1]<<" ";
			}
			//cerr<<"("<<i<<", "<<j<<") "<<query(pos, 1, n, 1)<<endl;
			median = min(median, query(pos, 1, n, 1));
		}
		// Cleanup
		for (int s=i; s<i+H; s++) {
			for (int t=C-W; t<C; t++) {
				update(Q[s][t], 0, 1, n, 1);
				//cerr<<"-"<<Q[s][t]<<" ";
			}
		}
		//cerr<<"(Cleanup)"<<endl;
	}
	return median;
}


// Full Solution: binary search

// int q[3001][3001];
// int r, c, h, w;

// v<v<int>> range;


// bool median_leq(int median) {
// 	for (int i=0; i<r; i++) {
// 		for (int j=0; j<c; j++) {
// 			range[i+1][j+1] = range[i][j+1] + range[i+1][j] - range[i][j];
// 			range[i+1][j+1] += (q[i][j]<=median)?1:0;
// 		}
// 	}
// 	for (int i=0; i<r-h+1; i++) {
// 		for (int j=0; j<c-w+1; j++) {
// 			if (range[i+h][j+w]-range[i][j+w]-range[i+h][j]+range[i][j] >= (h*w)/2+1) {
// 				//cerr<<"Median <= "<<median<<": "<<range[i+h][j+w]-range[i][j+w]-range[i+h][j]+range[i][j]<<" items found at ("<<i<<", "<<j<<")."<<endl;
// 				return true;
// 			}
// 		}
// 	}
// 	//cerr<<"Median > "<<median<<"."<<endl;
// 	return false;
// }

// int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
// 	//cerr<<R<<" "<<C<<" "<<H<<" "<<W<<" "<<(H*W)/2<<endl;
// 	for (int i=0; i<R; i++) {
// 		for (int j=0; j<C; j++) {
// 			q[i][j] = Q[i][j];
// 		}
// 	}
// 	r=R; c=C; h=H; w=W;
// 	range = v<v<int>> (R+1, v<int> (C+1, 0));

// 	int left=0, right=R*C-(H*W)/2;
// 	while (left+1<right) {
// 		int mid = (left+right)/2;
// 		if (median_leq(mid)){
// 			right = mid;
// 		} else {
// 			left = mid;
// 		}
// 	}
// 	return right;
// }

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