oj.uz

Submission #164294

# Submission time Handle Problem Language Result Execution time Memory
164294 2019-11-19T02:57:18 Z Anai Rectangles (IOI19_rect) C++14
0 / 100
 155 ms 148248 KB 
#include "rect.h"
#include <bits/stdc++.h>

#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<int, int>;

const int S = 2500 * 2500 + 5, N = 2505;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};


vector<pii> qs[N][N];
bool bad[N][N];

vector<pair<pii, pii>> trims;
vector<vector<int>> mx;
vector<vector<int>> lf, rt, bt, tp;
int n, m;


static void scanner() {
	lf = vector<vector<int>>(n, vector<int>(m));
	rt = vector<vector<int>>(n, vector<int>(m));
	tp = vector<vector<int>>(n, vector<int>(m));
	bt = vector<vector<int>>(n, vector<int>(m));

	for (int i = 0; i < n; ++i) {
		vector<int> stk;

		for (int j = 0; j < m; ++j) { // left
			while (!stk.empty() && mx[i][stk.back()] <= mx[i][j])
				stk.pop_back();
			lf[i][j] = stk.empty() ? -1 : stk.back();
			stk.push_back(j); }

		stk.clear();
		for (int j = m - 1; j > 0; --j) { // right
			while (!stk.empty() && mx[i][stk.back()] <= mx[i][j])
				stk.pop_back();
			rt[i][j] = stk.empty() ? -1 : stk.back();
			stk.push_back(j); } }

	for (int j = 0; j < m; ++j) {
		vector<int> stk;

		for (int i = 0; i < n - 1; ++i) { // top
			while (!stk.empty() && mx[stk.back()][j] <= mx[i][j])
				stk.pop_back();
			tp[i][j] = stk.empty() ? -1 : stk.back();
			stk.push_back(i); }

		stk.clear();
		for (int i = n - 1; i > 0; --i) { // bottom
			while (!stk.empty() && mx[stk.back()][j] <= mx[i][j])
				stk.pop_back();
			bt[i][j] = stk.empty() ? -1 : stk.back();
			stk.push_back(i); } } }

static void run_vertical() {
	vector<int> h_stk, stk[N];
	int h[N];

	for (int i = 1; i < n - 1; ++i)
	for (int j = 1; j < m - 1; ++j) {
		if (rt[i][j] == -1 || lf[i][j] == -1 || tp[i][j] == -1 || bt[i][j] == -1 || bad[i][j]) {
			bad[i][j] = true; }
		else {
			qs[tp[i][j]][rt[i][j] - 1].emplace_back(i, j);
			qs[bt[i][j]][rt[i][j] - 1].emplace_back(-i, -j); } }

	// bottom radiates up
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			while (!stk[j].empty() && mx[stk[j].back()][j] < mx[i][j])
				stk[j].pop_back();
			h[j] = stk[j].empty() ? 0 : stk[j].back();
			stk[j].push_back(i); }

		h_stk.clear();
		for (int j = 0; j < m; ++j) { 
			while (!h_stk.empty() && h[h_stk.back()] > h[j])
				h_stk.pop_back();
			h_stk.push_back(j);

			for (auto q: qs[i][j]) if (q.x < 0) { // actually query handling
				int pos = -1, bnd = lf[-q.x][-q.y];
				for (int msk = 1 << 11; msk > 0; msk/= 2)
					if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
						pos+= msk;
				pos+= 1;
				if (h[h_stk[pos]] > tp[-q.x][-q.y] && !bad[-q.x][-q.y])
					bad[-q.x][-q.y] = true; } } }

	for (int i = 0; i < N; ++i)
		stk[i].clear();

	// top radiates down
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < m; ++j) {
			while (!stk[j].empty() && mx[stk[j].back()][j] < mx[i][j])
				stk[j].pop_back();
			h[j] = stk[j].empty() ? 1e9 : stk[j].back();
			stk[j].push_back(i); }

		h_stk.clear();
		for (int j = 0; j < m; ++j) { 
			while (!h_stk.empty() && h[h_stk.back()] < h[j])
				h_stk.pop_back();
			h_stk.push_back(j);

			for (auto q: qs[i][j]) if (q.x > 0) { // actually query handling
				int pos = -1, bnd = lf[q.x][q.y];
				for (int msk = 1 << 11; msk > 0; msk/= 2)
					if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
						pos+= msk;
				pos+= 1;
				if (h[h_stk[pos]] < bt[q.x][q.y] && !bad[q.x][q.y])
					bad[q.x][q.y] = true; } } } }

static void run_horizontal() {
	vector<int> h_stk, stk[N];
	int h[N];

	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j)
		qs[i][j].clear();

	for (int i = 1; i < n - 1; ++i)
	for (int j = 1; j < m - 1; ++j) {
		if (rt[i][j] == -1 || lf[i][j] == -1 || tp[i][j] == -1 || bt[i][j] == -1 || bad[i][j]) {
			bad[i][j] = true; }
		else {
			qs[tp[i][j] + 1][lf[i][j]].emplace_back(i, j);
			qs[tp[i][j] + 1][rt[i][j]].emplace_back(-i, -j); } }

	// right radiates left
	for (int j = 0; j < m; ++j) {
		for (int i = 0; i < n; ++i) {
			while (!stk[i].empty() && mx[i][stk[i].back()] < mx[i][j])
				stk[i].pop_back();
			h[i] = stk[i].empty() ? 0 : stk[i].back();
			stk[i].push_back(j); }

		h_stk.clear();
		for (int i = 0; i < n; ++i) { 
			while (!h_stk.empty() && h[h_stk.back()] > h[i])
				h_stk.pop_back();
			h_stk.push_back(i);

			for (auto q: qs[i][j]) if (q.x < 0) { // actually query handling
				int pos = -1, bnd = lf[-q.x][-q.y];
				for (int msk = 1 << 11; msk > 0; msk/= 2)
					if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
						pos+= msk;
				pos+= 1;
				if (h[h_stk[pos]] > lf[-q.x][-q.y] && !bad[-q.x][-q.y])
					bad[-q.x][-q.y] = true; } } }

	for (int i = 0; i < N; ++i)
		stk[i].clear();

	// left radiates right
	for (int j = m - 1; j >= 0; --j) {
		for (int i = 0; i < n; ++i) {
			while (!stk[i].empty() && mx[i][stk[i].back()] < mx[i][j])
				stk[i].pop_back();
			h[i] = stk[i].empty() ? 1e9 : stk[i].back();
			stk[i].push_back(j); }

		h_stk.clear();
		for (int i = 0; i < n; ++i) { 
			while (!h_stk.empty() && h[h_stk.back()] < h[i])
				h_stk.pop_back();
			h_stk.push_back(i);

			for (auto q: qs[i][j]) if (q.x > 0) { // actually query handling
				int pos = -1, bnd = rt[q.x][q.y];
				for (int msk = 1 << 11; msk > 0; msk/= 2)
					if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
						pos+= msk;
				pos+= 1;
				if (h[h_stk[pos]] < rt[q.x][q.y] && !bad[q.x][q.y])
					bad[q.x][q.y] = true; } } } }

static void pulatronizate() {
	for (int i = 1; i + 1 < n; ++i)
	for (int j = 1; j + 1 < m; ++j) if (!bad[i][j]) {
		trims.emplace_back(pii(lf[i][j], tp[i][j]), pii(rt[i][j], bt[i][j])); } }

i64 count_rectangles(vector<vector<int>> _mx) {
	n = _mx.size(), m = _mx[0].size();
	swap(mx, _mx);

	scanner();
	run_vertical();
	run_horizontal();
	pulatronizate();

	sort(begin(trims), end(trims));
	trims.erase(unique(begin(trims), end(trims)), end(trims));

	return trims.size(); }

Compilation message

rect.cpp: In function 'void run_vertical()':
rect.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:118:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp: In function 'void run_horizontal()':
rect.cpp:157:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:183:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos + msk + 1 < h_stk.size() && h_stk[pos + msk] <= bnd)
          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 147832 KB Output is correct
2 Correct 153 ms 147960 KB Output is correct
3 Correct 150 ms 148020 KB Output is correct
4 Correct 146 ms 147832 KB Output is correct
5 Correct 146 ms 147960 KB Output is correct
6 Incorrect 145 ms 147960 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 147832 KB Output is correct
2 Correct 153 ms 147960 KB Output is correct
3 Correct 150 ms 148020 KB Output is correct
4 Correct 146 ms 147832 KB Output is correct
5 Correct 146 ms 147960 KB Output is correct
6 Incorrect 145 ms 147960 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 147832 KB Output is correct
2 Correct 153 ms 147960 KB Output is correct
3 Correct 150 ms 148020 KB Output is correct
4 Correct 146 ms 147832 KB Output is correct
5 Correct 146 ms 147960 KB Output is correct
6 Incorrect 145 ms 147960 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 147832 KB Output is correct
2 Correct 153 ms 147960 KB Output is correct
3 Correct 150 ms 148020 KB Output is correct
4 Correct 146 ms 147832 KB Output is correct
5 Correct 146 ms 147960 KB Output is correct
6 Incorrect 145 ms 147960 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 148188 KB Output is correct
2 Correct 145 ms 148216 KB Output is correct
3 Correct 155 ms 148076 KB Output is correct
4 Correct 146 ms 147804 KB Output is correct
5 Incorrect 149 ms 148248 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 147832 KB Output is correct
2 Correct 153 ms 147960 KB Output is correct
3 Correct 150 ms 148020 KB Output is correct
4 Correct 146 ms 147832 KB Output is correct
5 Correct 146 ms 147960 KB Output is correct
6 Incorrect 145 ms 147960 KB Output isn't correct
7 Halted 0 ms 0 KB -