oj.uz

Submission #317944

# Submission time Handle Problem Language Result Execution time Memory
317944 2020-10-31T01:22:24 Z MetB Rectangles (IOI19_rect) C++14
0 / 100
 2 ms 1408 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, m;

pair <int, int> hor_l[2500][2500], hor_r[2500][2500];
pair <int, int> ver_u[2500][2500], ver_d[2500][2500];

vector < array <int, 4> > v;
vector < array <int, 4> > bucket[2500];

struct window : vector < pair <int, int> > {
	void append (int x) {
		while (!empty () && back ().first < x) pop_back ();
	}
};

void check_above (pair <int, int>& p, int i, int l, int r) {
	if (!i) return;
	if (hor_l[i-1][r].first == l) {
		p.second = max (p.second, 1 + hor_l[i-1][r].second);
	}

	if (hor_r[i-1][l].first == r) {
		p.second = max (p.second, 1 + hor_r[i-1][l].second);
	}
}

void check_left (pair <int, int>& p, int u, int d, int j) {
	if (!j) return;
	if (ver_d[u][j-1].first == d) {
		p.second = max (p.second, 1 + ver_d[u][j-1].second);
	}

	if (ver_u[d][j-1].first == u) {
		p.second = max (p.second, 1 + ver_u[d][j-1].second);
	}
}

void check_rectangle (vector < vector <int> >& a, int x1, int y1, int x2, int y2) {
	if (x2 - x1 < 2 || y2 - y1 < 2) return;
	int hor_size, ver_size;

	if (a[x2-1][y1] <= a[x2-1][y2]) ver_size = hor_r[x2-1][y1].second;
	else ver_size = hor_l[x2-1][y2].second;

	if (a[x1][y2-1] <= a[x2][y2-1]) hor_size = ver_d[x1][y2-1].second;
	else hor_size = ver_u[x2][y2-1].second;

	if ((hor_size >= y2 - y1 - 1) && (ver_size >= x2 - x1 - 1)) {
		v.push_back ({x1, y1, x2, y2});
	}
}

ll count_rectangles (vector<vector<int> > a) {
	n = a.size (), m = a[0].size ();

	window s;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			s.append (a[i][j]);
			if (!s.empty ()) {
				int l = s.back ().second, r = j;
				hor_l[i][r].first = l;
				hor_l[i][r].second = 1;

				check_above (hor_l[i][r], i, l, r);
			} else hor_l[i][j].first = -1;
			s.push_back ({a[i][j], j});
		}

		s.clear ();

		for (int j = m - 1; j >= 0; j--) {
			s.append (a[i][j]);
			if (!s.empty ()) {
				int l = j, r = s.back ().second;
				hor_r[i][l].first = r;
				hor_r[i][l].second = 1;

				check_above (hor_r[i][l], i, l, r);
			} else hor_r[i][j].first = -1;
			s.push_back ({a[i][j], j});
		}
	}

	for (int j = 0; j < m; j++) {
		
		s.clear ();

		for (int i = 0; i < n; i++) {
			s.append (a[i][j]);
			if (!s.empty ()) {
				int u = s.back ().second, d = i;
				ver_u[d][j].first = u;
				ver_u[d][j].second = 1;

				check_left (ver_u[d][j], u, d, j);
			} else ver_u[i][j].first = -1;
			s.push_back ({a[i][j], i});
		}

		s.clear ();

		for (int i = n - 1; i >= 0; i--) {
			s.append (a[i][j]);
			if (!s.empty ()) {
				int u = i, d = s.back ().second;
				ver_d[u][j].first = d;
				ver_d[u][j].second = 1;

				check_left (ver_d[u][j], u, d, j);
			} else ver_d[i][j].first = -1;
			s.push_back ({a[i][j], i});
		}
	}

	int x;

	for (int i = 1; i < n - 1; i++) {
		for (int j = 0; j < m; j++) {
			if (hor_l[i][j].first != -1) {
				int l = hor_l[i][j].first, r = j;
				
				x = ver_u[i+1][l+1].first;
				if (l < r && x != -1) check_rectangle (a, x, l, i + 1, r);
				
				x = ver_d[i-1][l+1].first;
				if (l < r && x != -1) check_rectangle (a, i - 1, l, x, r);
				
				x = ver_u[i+1][r-1].first;
				if (l < r && x != -1) check_rectangle (a, x, l, i + 1, r);
				
				x = ver_d[i-1][r-1].first;
				if (l < r && x != -1) check_rectangle (a, i - 1, l, x, r);
			}


			if (hor_r[i][j].first != -1) {
				int l = j, r = hor_r[i][j].first;

				x = ver_u[i+1][l+1].first;
				if (l < r && x != -1) check_rectangle (a, x, l, i + 1, r);
				
				x = ver_d[i-1][l+1].first;
				if (l < r && x != -1) check_rectangle (a, i - 1, l, x, r);
				
				x = ver_u[i+1][r-1].first;
				if (l < r && x != -1) check_rectangle (a, x, l, i + 1, r);
				
				x = ver_d[i-1][r-1].first;
				if (l < r && x != -1) check_rectangle (a, i - 1, l, x, r);
			}
		}
	}

	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < max (n, m); i++)
			bucket[i].clear ();

		for (auto&& a : v) {
			bucket[a[k]].push_back (a);
		}

		v.clear ();

		for (int i = 0; i < max (n, m); i++)
			for (auto&& a : bucket[i])
				v.push_back (a);		
	}

	int cnt = 0;

	for (int i = 0; i < (int) v.size (); i++)
		if (!i || v[i-1] != v[i]) cnt++;

	return cnt;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Incorrect 1 ms 896 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Incorrect 1 ms 896 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Incorrect 1 ms 896 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Incorrect 1 ms 896 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1408 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 2 ms 896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Incorrect 1 ms 896 KB Output isn't correct
7 Halted 0 ms 0 KB -