제출 #302642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302642		wilwxk	Rectangles (IOI19_rect)	C++17	72 / 100	5086 ms	809032 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
// #define debug printf
#define debug // 
typedef long long ll;

const int MAXN = 2505;
vector<vector<int> > input;
int seg[4][MAXN][MAXN*4];
int mx[4][MAXN][MAXN];
int mxe[4][MAXN][MAXN];
int n, m;

void build(int k, int id, int sind, int ini, int fim) {
	// debug("build %d %d %d %d %d\n", k, id, sind, ini, fim);
	if (ini == fim) {
		if (k&1) seg[k][id][sind] = mx[k][id][ini];
		else seg[k][id][sind] = mx[k][ini][id];
		// debug("bloh 3\n");
		return;
	}
	int mid = (ini+fim)/2;
	int e = sind*2;
	int d = e+1;
	build(k, id, e, ini, mid);
	// debug("bloh 1\n");
	build(k, id, d, mid+1, fim);
	// debug("bloh 2\n");
	if (k == 0 || k == 3) seg[k][id][sind] = min(seg[k][id][e], seg[k][id][d]);
	else seg[k][id][sind] = max(seg[k][id][e], seg[k][id][d]);
}

int query(int k, int id, int sind, int l, int r, int ql, int qr) {
	if (ql > r || qr < l) return (k == 0 || k == 3) ? MAXN : -1;
	if (ql <= l && qr >= r) return seg[k][id][sind];
	int mid = (l+r)/2;
	int e = sind*2;
	int d = e+1;
	if (k == 0 || k == 3) return min(query(k, id, e, l, mid, ql, qr), query(k, id, d, mid+1, r, ql, qr));
	return max(query(k, id, e, l, mid, ql, qr), query(k, id, d, mid+1, r, ql, qr));
}

void precalc() {

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			mxe[0][i][j] = m;
			mxe[1][i][j] = 1;
			mxe[2][i][j] = 1;
			mxe[3][i][j] = n;
		}
	}

	stack<int> st;
	// ------------->
	for (int i = 0; i < n; i++) {
		st.push(m);
		for (int j = m-1; j >= 0; j--) {
			while (st.top() != m && input[i][st.top()] < input[i][j]) {
				mxe[2][i+1][st.top()+1] = (j+1)+1;
				st.pop();
			}
			mx[0][i+1][j+1] = (st.top()-1)+1;
			st.push(j);
		}
	}
	// ^^^^^^^^^^^^^
	while (st.size()) st.pop();
	for (int j = 0; j < m; j++) {
		st.push(-1);
		for (int i = 0; i < n; i++) {
			while (st.top() != -1 && input[st.top()][j] < input[i][j]) {
				mxe[3][st.top()+1][j+1] = (i-1)+1;
				st.pop();
			}
			mx[1][i+1][j+1] = (st.top()+1)+1;
			st.push(i);
		}
	}
	// <------------
	while (st.size()) st.pop();
	for (int i = 0; i < n; i++) {
		st.push(-1);
		for (int j = 0; j < m; j++) {
			while (st.top() != -1 && input[i][st.top()] < input[i][j]) {
				mxe[0][i+1][st.top()+1] = (j-1)+1;
				st.pop();
			}
			mx[2][i+1][j+1] = (st.top()+1)+1;
			st.push(j);
		}
	}
	// vvvvvvvvvvvv
	while (st.size()) st.pop();
	for (int j = 0; j < m; j++) {
		st.push(n);
		for (int i = n-1; i >= 0; i--) {
			while (st.top() != n && input[st.top()][j] < input[i][j]) {
				mxe[1][st.top()+1][j+1] = (i+1)+1;
				st.pop();
			}
			mx[3][i+1][j+1] = (st.top()-1)+1;
			st.push(i);
		}
	}

	for (int k = 0; k < 4; k++) {
		debug("---k = %d---\n", k);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) debug("%d ", mxe[k][i][j]);
			debug("\n");
		}
	}

	for (int i = 1; i <= n; i++) {
		build(1, i, 1, 1, m);
		// debug("bleh\n");
		build(3, i, 1, 1, m);
	}
		// debug("bleh2\n");
	for (int i = 1; i <= m; i++) {
		build(0, i, 1, 1, n);
		build(2, i, 1, 1, n);
	}

}

bool check(int a, int b, int c, int d) {
	if (a == m || b == 1 || c == 1 || d == n) return 0;
	debug("check %d %d %d %d\n", a, b, c, d);
	// >>>>>>>>>>>>
	int aa = query(0, c-1, 1, 1, n, b, d);
	// ^^^^^^^^^^^^
	int bb = query(1, d+1, 1, 1, m, c, a);
	// <<<<<<<<<<<<
	int cc = query(2, a+1, 1, 1, n, b, d);
	// vvvvvvvvvvvv
	int dd = query(3, b-1, 1, 1, m, c, a);
	debug("// %d %d %d %d\n", aa, bb, cc, dd);
	if (aa < a) return 0;
	if (bb > b) return 0;
	if (cc > c) return 0;
	if (dd < d) return 0;
	debug("good %d %d %d %d\n", a, b, c, d);
	return 1;
}

long long count_rectangles(vector<vector<int> > INPUT) {
	n = INPUT.size();
	m = INPUT[0].size();
	input = INPUT;

	precalc();

	vector<tuple<int, int, int, int> > possi;
	for (int i = 2; i <= n-1; i++) {
		for (int j = 2; j <= m-1; j++) {
			int a = mxe[0][i][j];
			int b = mxe[1][i][j];
			int c = mxe[2][i][j];
			int d = mxe[3][i][j];
			possi.push_back({a, b, c, d});
		}
	}
	sort(possi.begin(), possi.end());
	auto it = unique(possi.begin(), possi.end());
	possi.resize(it-possi.begin());

	ll ans = 0;
	for (auto rec : possi) {
		int a, b, c, d;
		tie(a, b, c, d) = rec;
		ans += check(a, b, c, d);
	}

	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'void precalc()':
rect.cpp:109:9: warning: left operand of comma operator has no effect [-Wunused-value]
  109 |   debug("---k = %d---\n", k);
      |         ^~~~~~~~~~~~~~~~
rect.cpp:111:39: warning: left operand of comma operator has no effect [-Wunused-value]
  111 |    for (int j = 1; j <= m; j++) debug("%d ", mxe[k][i][j]);
      |                                       ^~~~~
rect.cpp:112:10: warning: statement has no effect [-Wunused-value]
  112 |    debug("\n");
      |         ~^~~~~
rect.cpp: In function 'bool check(int, int, int, int)':
rect.cpp:131:8: warning: left operand of comma operator has no effect [-Wunused-value]
  131 |  debug("check %d %d %d %d\n", a, b, c, d);
      |        ^~~~~~~~~~~~~~~~~~~~~
rect.cpp:131:34: warning: right operand of comma operator has no effect [-Wunused-value]
  131 |  debug("check %d %d %d %d\n", a, b, c, d);
      |                                  ^
rect.cpp:131:37: warning: right operand of comma operator has no effect [-Wunused-value]
  131 |  debug("check %d %d %d %d\n", a, b, c, d);
      |                                     ^
rect.cpp:131:40: warning: right operand of comma operator has no effect [-Wunused-value]
  131 |  debug("check %d %d %d %d\n", a, b, c, d);
      |                                        ^
rect.cpp:140:8: warning: left operand of comma operator has no effect [-Wunused-value]
  140 |  debug("// %d %d %d %d\n", aa, bb, cc, dd);
      |        ^~~~~~~~~~~~~~~~~~
rect.cpp:140:32: warning: right operand of comma operator has no effect [-Wunused-value]
  140 |  debug("// %d %d %d %d\n", aa, bb, cc, dd);
      |                                ^~
rect.cpp:140:36: warning: right operand of comma operator has no effect [-Wunused-value]
  140 |  debug("// %d %d %d %d\n", aa, bb, cc, dd);
      |                                    ^~
rect.cpp:140:40: warning: right operand of comma operator has no effect [-Wunused-value]
  140 |  debug("// %d %d %d %d\n", aa, bb, cc, dd);
      |                                        ^~
rect.cpp:145:8: warning: left operand of comma operator has no effect [-Wunused-value]
  145 |  debug("good %d %d %d %d\n", a, b, c, d);
      |        ^~~~~~~~~~~~~~~~~~~~
rect.cpp:145:33: warning: right operand of comma operator has no effect [-Wunused-value]
  145 |  debug("good %d %d %d %d\n", a, b, c, d);
      |                                 ^
rect.cpp:145:36: warning: right operand of comma operator has no effect [-Wunused-value]
  145 |  debug("good %d %d %d %d\n", a, b, c, d);
      |                                    ^
rect.cpp:145:39: warning: right operand of comma operator has no effect [-Wunused-value]
  145 |  debug("good %d %d %d %d\n", a, b, c, d);
      |                                       ^

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28