Submission #153545

#	Time	Username	Problem	Language	Result	Execution time	Memory
153545		myungwoo	Rectangles (IOI19_rect)	C++14	72 / 100	5089 ms	548352 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

#define fr first
#define sc second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;
typedef pair<int, int> pii;

int N, M;
int A[2502][2502];
pii ver[2502][2502], hor[2502][2502];

struct SEGMENT {
	int a, b, t, dp;
	bool operator < (const SEGMENT &ot)const{
		if (t != ot.t) return t < ot.t;
		if (a != ot.a) return a < ot.a;
		return b < ot.b;
	}
	bool operator == (const SEGMENT &ot)const{
		return a == ot.a && b == ot.b && t == ot.t;
	}
	bool operator != (const SEGMENT &ot)const{
		return a != ot.a || b != ot.b || t != ot.t;
	}
};

lld count_rectangles(vector<vector<int> > a)
{
	N = sz(a); M = sz(a[0]);
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) A[i][j] = a[i-1][j-1];
	vector <SEGMENT> vertical, horizontal;
	for (int i=1;i<=N;i++){
		{
			stack <int> stk;
			for (int j=1;j<=M;j++){
				while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
				hor[i][j].fr = stk.empty() ? 1 : stk.top()+1;
				stk.push(j);
			}
		}
		{
			stack <int> stk;
			for (int j=M;j;j--){
				while (!stk.empty() && A[i][stk.top()] <= A[i][j]) stk.pop();
				hor[i][j].sc = stk.empty() ? M : stk.top()-1;
				stk.push(j);
			}
		}
		for (int j=1;j<=M;j++) horizontal.pb({hor[i][j].fr, hor[i][j].sc, i});
	}
	for (int j=1;j<=M;j++){
		{
			stack <int> stk;
			for (int i=1;i<=N;i++){
				while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
				ver[i][j].fr = stk.empty() ? 1 : stk.top()+1;
				stk.push(i);
			}
		}
		{
			stack <int> stk;
			for (int i=N;i;i--){
				while (!stk.empty() && A[stk.top()][j] <= A[i][j]) stk.pop();
				ver[i][j].sc = stk.empty() ? N : stk.top()-1;
				stk.push(i);
			}
		}
		for (int i=1;i<=N;i++) vertical.pb({ver[i][j].fr, ver[i][j].sc, j});
	}

	sort(all(horizontal));
	sort(all(vertical));
	for (int i=0,j=0;i<sz(horizontal);i++){
		auto &sg = horizontal[i]; sg.dp = 1;
		while (horizontal[j] < SEGMENT{sg.a, sg.b, sg.t-1}) j++;
		if (horizontal[j] == SEGMENT{sg.a, sg.b, sg.t-1}) sg.dp = horizontal[j].dp+1;
	}
	for (int i=0,j=0;i<sz(vertical);i++){
		auto &sg = vertical[i]; sg.dp = 1;
		while (vertical[j] < SEGMENT{sg.a, sg.b, sg.t-1}) j++;
		if (vertical[j] == SEGMENT{sg.a, sg.b, sg.t-1}) sg.dp = vertical[j].dp+1;
	}

	set <tuple<int, int, int, int>> vis;
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		int sy = ver[i][j].fr, ey = ver[i][j].sc;
		int sx = hor[i][j].fr, ex = hor[i][j].sc;

		if (sy == 1 || sx == 1 || ey == N || ex == M) continue;
		auto tp = make_tuple(sy, sx, ey, ex);
		if (vis.count(tp)) continue;
		{
			auto it = lower_bound(all(vertical), SEGMENT{sy, ey, ex});
			if (it == vertical.end() || *it != SEGMENT{sy, ey, ex} || it->dp <= ex-sx) continue;
		}
		{
			auto it = lower_bound(all(horizontal), SEGMENT{sx, ex, ey});
			if (it == horizontal.end() || *it != SEGMENT{sx, ex, ey} || it->dp <= ey-sy) continue;
		}
		vis.insert(tp);
	}
	return sz(vis);
}

• 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