oj.uz

Submission #740013

# Submission time Handle Problem Language Result Execution time Memory
740013 2023-05-11T23:22:35 Z fractlpaca Quality Of Living (IOI10_quality) C++17
100 / 100
 1277 ms 147012 KB 
#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;
// }

// 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 12 ms 3712 KB Output is correct
8 Correct 20 ms 4216 KB Output is correct
9 Correct 11 ms 4040 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 12 ms 3712 KB Output is correct
8 Correct 20 ms 4216 KB Output is correct
9 Correct 11 ms 4040 KB Output is correct
10 Correct 140 ms 26816 KB Output is correct
11 Correct 146 ms 26812 KB Output is correct
12 Correct 72 ms 17432 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 12 ms 3712 KB Output is correct
8 Correct 20 ms 4216 KB Output is correct
9 Correct 11 ms 4040 KB Output is correct
10 Correct 140 ms 26816 KB Output is correct
11 Correct 146 ms 26812 KB Output is correct
12 Correct 72 ms 17432 KB Output is correct
13 Correct 1277 ms 138936 KB Output is correct
14 Correct 1144 ms 138964 KB Output is correct
15 Correct 1131 ms 147012 KB Output is correct