Submission #205423

#	Time	Username	Problem	Language	Result	Execution time	Memory
205423		jasony123123	Quality Of Living (IOI10_quality)	C++14	100 / 100	2929 ms	140424 KiB

quality

#include "quality.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

int _R, _C, _H, _W;
int T[3001][3001];

int get(int r1, int c1, int r2, int c2) {
	return T[r1][c1] - T[r2 + 1][c1] - T[r1][c2 + 1] + T[r2 + 1][c2 + 1];
}
bool test(int x, int Q[][3001]) {
	RFORE(r, _R - 1, 0)RFORE(c, _C - 1, 0) {
		T[r][c] = T[r + 1][c] + T[r][c + 1] - T[r + 1][c + 1];
		if (Q[r][c] < x) T[r][c]--;
		else if (Q[r][c] > x) T[r][c]++;
	}
	FOR(r, 0, _R - _H + 1)FOR(c, 0, _C - _W + 1)
		if (get(r, c, r + _H - 1, c + _W - 1) <= 0) return true;
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	_R = R, _C = C, _H = H, _W = W;
	int lo = 1, hi = R*C;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (test(mid, Q) == true) hi = mid;
		else lo = mid + 1;
	}
	return lo;
}

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