Submission #153777

#	Time	Username	Problem	Language	Result	Execution time	Memory
153777		myungwoo	Rectangles (IOI19_rect)	C++14	59 / 100	5101 ms	495096 KiB

rect

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

#define fr first
#define sc second
#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;
	}
};
vector <SEGMENT> container;
bool cmp_segment(const int &a, const int &b){
	return container[a] < container[b];
}

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];
	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);
		}
		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++){
		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);
		}
		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);
		}
	}
	vector <int> vertical, horizontal;
	for (int j=1;j<=M;j++) for (int i=1;i<=N;i++){
		const auto &sg = ver[i][j];
		vertical.push_back(sz(container));
		container.push_back({sg.fr, sg.sc, j});
	}
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		const auto &sg = hor[i][j];
		horizontal.push_back(sz(container));
		container.push_back({sg.fr, sg.sc, i});
	}
	sort(all(vertical), cmp_segment);
	sort(all(horizontal), cmp_segment);
	const auto do_dp = [](const vector<int> &arr){
		for (auto i=arr.begin(),j=i;i!=arr.end();i++){
			static auto f = [](int p, int q){
				const auto &a = container[p];
				auto b = container[q]; b.t--;
				return a < b;
			};
			while (f(*j, *i)) j++;
			auto &p = container[*j], &q = container[*i];
			if (p.t == q.t-1 && p.a == q.a && p.b == q.b) q.dp = p.dp+1;
			else q.dp = 1;
		}
	};
	do_dp(vertical);
	do_dp(horizontal);


	const auto get = [](const vector<int> &arr, int a, int b, int t){
		SEGMENT sg = {a, b, t};
		int s = 0, e = sz(arr)-1, ret = sz(arr);
		while (s <= e){
			int m = s+e >> 1;
			auto &v = container[arr[m]];
			if (v < sg) s = m+1;
			else ret = m, e = m-1;
		}
		if (ret == sz(arr)) return 0;
		auto &v = container[arr[ret]];
		if (v.t == t && v.a == a && v.b == b) return v.dp;
		return 0;
	};
	set <lld> 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 || ey == N || sx == 1 || ex == M) continue;
		if (get(vertical, sy, ey, ex) <= ex-sx || get(horizontal, sx, ex, ey) <= ey-sy) continue;
		lld v = (lld)((sy-1)*M+sx-1)*N*M + (ey-1)*M+ex-1;
		if (vis.count(v)) continue;
		vis.insert(v);
	}
	return sz(vis);
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = s+e >> 1;
            ~^~

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