Submission #295901

#	Time	Username	Problem	Language	Result	Execution time	Memory
295901		ChrisT	Rectangles (IOI19_rect)	C++17	23 / 100	4672 ms	783688 KiB

rect

#include <bits/stdc++.h> 
#include "rect.h"
using namespace std; 
const int MN = 1e5+5; 
#define mp make_pair
struct Rect {
	int bx,ry,tx,ly;
	Rect (int x, int y, int x2, int y2) {
		bx = max(x,x2); ry = max(y,y2); tx = min(x,x2); ly = min(y,y2);
	}
	bool operator< (const Rect &o) const {
		return mp(bx,mp(ry,mp(tx,ly))) < mp(o.bx,mp(o.ry,mp(o.tx,o.ly)));
	}
	bool operator== (const Rect &o) const {
		return bx == o.bx && ry == o.ry && tx == o.tx && ly == o.ly;
	}
};
long long count_rectangles (vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	vector<vector<int>> nextLeft(n,vector<int>(m,1e9)), nextRight(n,vector<int>(m,-1)), nextUp(n,vector<int>(m,1e9)), nextDown(n,vector<int>(m,-1)), upFromLeft(n,vector<int>(m)),upFromRight(n,vector<int>(m)),leftFromDown(n,vector<int>(m)),leftFromUp(n,vector<int>(m));
	for (int i = 0; i < n; i++) {
		vector<int> stk;
		for (int j = 0; j < m; j++) {
			while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
			if (!stk.empty()) {
				nextLeft[i][j] = stk.back();
				upFromLeft[i][j] = 1;
				if (i > 0 && nextLeft[i-1][j] == nextLeft[i][j]) upFromLeft[i][j] += upFromLeft[i-1][j];
				else if (i > 0 && nextRight[i-1][stk.back()] == j) upFromLeft[i][j] += upFromRight[i-1][stk.back()];
			}
			stk.push_back(j);
		}
		stk.clear();
		for (int j = m-1; j >= 0; j--) {
			while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
			if (!stk.empty()) {
				nextRight[i][j] = stk.back();
				upFromRight[i][j] = 1;
				if (i > 0 && nextRight[i-1][j] == nextRight[i][j]) upFromRight[i][j] += upFromRight[i-1][j];
				else if (i > 0 && nextLeft[i-1][stk.back()] == j) upFromRight[i][j] += upFromLeft[i-1][stk.back()];
			}
			stk.push_back(j);
		}
	}
	for (int j = 0; j < m; j++) {
		vector<int> stk;
		for (int i = 0; i < n; i++) {
			while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
			if (!stk.empty()) {
				nextUp[i][j] = stk.back();
				leftFromUp[i][j] = 1;
				if (j > 0 && nextUp[i][j-1] == nextUp[i][j]) leftFromUp[i][j] += leftFromUp[i][j-1];
				else if (j > 0 && nextDown[stk.back()][j-1] == i) leftFromUp[i][j] += leftFromDown[stk.back()][j-1];
			}
			stk.push_back(i);
		}
		stk.clear();
		for (int i = n-1; i >= 0; i--) {
			while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
			if (!stk.empty()) {
				nextDown[i][j] = stk.back();
				leftFromDown[i][j] = 1;
				if (j > 0 && nextDown[i][j-1] == nextDown[i][j]) leftFromDown[i][j] += leftFromDown[i][j-1];
				else if (j > 0 && nextUp[stk.back()][j-1] == i) leftFromDown[i][j] += leftFromUp[stk.back()][j-1];
			}
			stk.push_back(i);
		}
	}
	auto works = [&] (int bx, int ry, int tx, int ly) {
		return ((nextLeft[bx-1][ry] == ly && bx - upFromLeft[bx-1][ry] <= tx + 1) || (nextRight[bx-1][ly] == ry && bx - upFromRight[bx-1][ly] <= tx + 1)) && ((nextUp[bx][ry-1] == tx && ry - leftFromUp[bx][ry-1] <= ly + 1) || (nextDown[tx][ry-1] == bx && ry - leftFromDown[tx][ry-1] <= ly + 1));
	};
	int ret = 0;
	vector<Rect> can;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i > 0 && j > 0) can.emplace_back(i,j,nextUp[i][j-1],nextLeft[i-1][j]);
			if (i > 0 && j+1 < m) can.emplace_back(i,j,nextUp[i][j+1],nextRight[i-1][j]);
			if (i+1 < n && j > 0) can.emplace_back(i,j,nextDown[i][j-1],nextLeft[i+1][j]);
			if (i+1 < n && j+1 < m) can.emplace_back(i,j,nextDown[i][j+1],nextRight[i+1][j]);
		}
	}
	sort(can.begin(),can.end()); can.erase(unique(can.begin(),can.end()),can.end());
	for (Rect &r : can) {
		if (abs(r.bx - r.tx) <= 1 || abs(r.ly - r.ry) <= 1) continue;
		for (int i : {r.bx,r.tx,r.ly,r.ry}) if (i < 0 || i > 1e8) goto fail;
		ret += works(r.bx,r.ry,r.tx,r.ly);
		fail:;
	}
	return ret;
}

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