Submission #449968

#	Time	Username	Problem	Language	Result	Execution time	Memory
449968		ComPhyPark	Rectangles (IOI19_rect)	C++14	72 / 100	5080 ms	311136 KiB

rect

#include"rect.h"
#include<queue>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
const ll M = 3000;
const int N = 3000;
ll hsh(int r, int e, int s) {
	return (e + M * s) * M + r;
}
ll ahsh(int gs, int ge, int ss, int se) {
	return gs + M * (ge + M * (ss + M * se));
}
vector<vector<int>>gl, gr, sl, sr;
vector<int>v;
vector<ll>ast, v1, v2;
vector<ll>::iterator it;
ll count_rectangles(vector<vector<int>>a) {
	int i, j, n = a.size(), m = a[0].size();
	gl.resize(n);
	gr.resize(n);
	for (i = 0; i < n; i++) {
		gl[i].resize(m);
		gr[i].resize(m);
		v.clear();
		for (j = 0; j < m; j++) {
			while (v.size() && a[i][v.back()] < a[i][j])v.pop_back();
			if (v.size())if (j > v.back() + 1)v1.push_back(hsh(i, v.back(), j));
			if (v.size() && a[i][v.back()] == a[i][j])v.pop_back();
			gl[i][j] = v.size() ? v.back() : -1;
			v.push_back(j);
		}
		v.clear();
		for (j = m - 1; j >= 0; j--) {
			while (v.size() && a[i][v.back()] < a[i][j])v.pop_back();
			if (v.size())if (j < v.back() - 1 && a[i][v.back()] != a[i][j])v1.push_back(hsh(i, j, v.back()));
			if (v.size() && a[i][v.back()] == a[i][j])v.pop_back();
			gr[i][j] = v.size() ? v.back() : -1;
			v.push_back(j);
		}
	}
	sl.resize(m);
	sr.resize(m);
	for (i = 0; i < m; i++) {
		sl[i].resize(n);
		sr[i].resize(n);
		v.clear();
		for (j = 0; j < n; j++) {
			while (v.size() && a[v.back()][i] < a[j][i])v.pop_back();
			if (v.size())if (j > v.back() + 1)v2.push_back(hsh(i, v.back(), j));
			if (v.size() && a[v.back()][i] == a[j][i])v.pop_back();
			sl[i][j] = v.size() ? v.back() : -1;
			v.push_back(j);
		}
		v.clear();
		for (j = n - 1; j >= 0; j--) {
			while (v.size() && a[v.back()][i] < a[j][i])v.pop_back();
			if (v.size())if (j < v.back() - 1 && a[v.back()][i] != a[j][i])v2.push_back(hsh(i, j, v.back()));
			if (v.size() && a[v.back()][i] == a[j][i])v.pop_back();
			sr[i][j] = v.size() ? v.back() : -1;
			v.push_back(j);
		}
	}
	v1.push_back(hsh(N - 1, N - 1, N - 1));
	v2.push_back(hsh(N - 1, N - 1, N - 1));
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	int gs, ge, ss, se;
	for (i = 1; i < n - 1; i++) {
		for (j = 1; j < m - 1; j++) {
			gs = gl[i][j];
			ge = gr[i][j];
			ss = sl[j][i];
			se = sr[j][i];
			if (gs == -1 || ge == -1 || ss == -1 || se == -1)continue;
			//printf("ssapPossible %d %d\n", i, j);
			//printf("[%d %d %d %d]\n", gs, ge, ss, se);
			it = lower_bound(v1.begin(), v1.end(), hsh(se - 1, gs, ge));
			if (hsh(se - 1, gs, ge) != *it)continue;
			if (it - v1.begin() < (se - ss - 2))continue;
			it -= (se - ss - 2);
			if (hsh(ss + 1, gs, ge) != *it)continue;
			it = lower_bound(v2.begin(), v2.end(), hsh(ge - 1, ss, se));
			if (hsh(ge - 1, ss, se) != *it)continue;
			if (it - v2.begin() < (ge - gs - 2))continue;
			it -= (ge - gs - 2);
			if (hsh(gs + 1, ss, se) != *it)continue;
			//printf("values correct\n");
			//printf("realPossible %d %d\n", i, j);
			ast.push_back(ahsh(gs, ge, ss, se));
		}
	}
	sort(ast.begin(), ast.end());
	ll r = ast.size();
	for (i = 1; i < ast.size(); i++) {
		if (ast[i - 1] == ast[i])r--;
	}
	return r;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (i = 1; i < ast.size(); i++) {
      |              ~~^~~~~~~~~~~~

• 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