oj.uz

Submission #205423

# Submission time Handle Problem Language Result Execution time Memory
205423 2020-02-28T22:55:27 Z jasony123123 Quality Of Living (IOI10_quality) C++14
100 / 100
 2929 ms 140424 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 29 ms 4036 KB Output is correct
8 Correct 29 ms 3960 KB Output is correct
9 Correct 26 ms 3832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 29 ms 4036 KB Output is correct
8 Correct 29 ms 3960 KB Output is correct
9 Correct 26 ms 3832 KB Output is correct
10 Correct 313 ms 23008 KB Output is correct
11 Correct 299 ms 22904 KB Output is correct
12 Correct 162 ms 15736 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 29 ms 4036 KB Output is correct
8 Correct 29 ms 3960 KB Output is correct
9 Correct 26 ms 3832 KB Output is correct
10 Correct 313 ms 23008 KB Output is correct
11 Correct 299 ms 22904 KB Output is correct
12 Correct 162 ms 15736 KB Output is correct
13 Correct 2929 ms 140424 KB Output is correct
14 Correct 2900 ms 140288 KB Output is correct
15 Correct 2669 ms 133360 KB Output is correct