Submission #156300

#	Time	Username	Problem	Language	Result	Execution time	Memory
156300		wilwxk	Rectangles (IOI19_rect)	C++14	0 / 100	44 ms	41080 KiB

rect

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

const int MAXN=2503;
int v[MAXN][MAXN];
short limite[MAXN][MAXN][4];
short seg[4][MAXN][4*MAXN];
int n, m, respf;

void histoi() {
	for(int i=0; i<n; i++) {
		stack<pair<int, int> > st;
		for(int j=0; j<m; j++) {
			while(st.size()&&st.top().first<v[i][j]) st.pop();
			limite[i][j][2]= st.size() ? st.top().second : -1;
			st.push({v[i][j], j});
		}
		while(st.size()) st.pop();
		for(int j=m-1; j>=0; j--) {
			while(st.size()&&st.top().first<v[i][j]) st.pop();
			limite[i][j][0]= st.size() ? st.top().second : m;
			st.push({v[i][j], j});
		}
	}
}

void histoj() {
	for(int j=0; j<m; j++) {
		stack<pair<int, int> > st;
		for(int i=0; i<n; i++) {
			while(st.size()&&st.top().first<v[i][j]) st.pop();
			limite[i][j][1]= st.size() ? st.top().second : -1;
			st.push({v[i][j], i});
		}
		while(st.size()) st.pop();
		for(int i=n-1; i>=0; i--) {
			while(st.size()&&st.top().first<v[i][j]) st.pop();
			limite[i][j][3]= st.size() ? st.top().second : n;
			st.push({v[i][j], i});
		}
	}
}

void junta(int sind, int e, int d, int k, int k2) {
	if(k==0||k==3) seg[k][k2][sind]=min(seg[k][k2][e], seg[k][k2][e]);
	else seg[k][k2][sind]=max(seg[k][k2][e], seg[k][k2][e]);
}

void build(int sind, int ini, int fim, int k, int k2) {
	if(ini==fim) {
		if(k==0) seg[k][k2][sind]=v[k2][ini];
		else seg[k][k2][sind]=v[ini][k2];
		return;
	}
	int mid=(ini+fim)/2;
	int e=sind*2; int d=e+1;
	build(e, ini, mid, k, k2); build(d, mid+1, fim, k, k2);
	junta(sind, e, d, k, k2);
} 

void query(int sind, int ini, int fim, int qini, int qfim, int k, int k2) {
	if(sind==1) {
		if(k==0||k==3) seg[k][k2][0]=MAXN;
		else seg[k][k2][0]=-1;
	}
	if(qini<=ini&&qfim>=fim) {
		junta(0, 0, sind, k, k2);
		return;
	}
	int mid=(ini+fim)/2;
	int e=sind*2; int d=e+1;
	if(qini<=mid) query(e, ini, mid, qini, qfim, k, k2);
	if(qfim>mid) query(d, mid+1, fim, qini, qfim, k, k2);
}

bool checa(int a, int b, int c, int d) {
	int i, j, i2, j2;
	i=min(a, c); i2=max(a, c);
	j=min(b, d); j2=max(b, d);
	if(i<0||j<0||i2>n-1||j2>m-1) return 0;
	// printf("checa %d %d %d %d\n", i, j, i2, j2);

	query(1, 0, m-1, j+1, j2-1, 3, i);
	int aa=seg[3][i][0];
	if(aa<i2-1) return 0;

	query(1, 0, m-1, j+1, j2-1, 1, i2);
	int bb=seg[1][i2][0];
	if(bb>i+1) return 0;

	query(1, 0, n-1, i+1, i2-1, 0, j);
	int cc=seg[0][j][0];
	if(cc<j2-1) return 0;

	query(1, 0, n-1, i+1, i2-1, 2, j2);
	int dd=seg[2][j2][0];
	if(dd>j+1) return 0;

	return 1;
}

ll count_rectangles(vector< vector<int> > A) {
	n=A.size(); m=A[0].size();
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			v[i][j]=A[i][j];
		}
	}
	histoi(); histoj();
	// for(int i=0; i<n; i++) {
	// 	for(int j=0; j<m; j++) printf("%d ", limite[i][j][3]);
	// 	printf("\n");
	// }

	for(int i=0; i<n; i++) build(1, 0, m-1, 0, i), build(1, 0, m-1, 2, i);
	for(int i=0; i<m; i++) build(1, 0, n-1, 1, i), build(1, 0, n-1, 3, i);

	for(int ii=1; ii<n-1; ii++) {
		for(int jj=1; jj<m-1; jj++) {
			// printf("%d %d\n", ii, jj);
			int i=limite[ii][jj][1];
			int j=limite[ii][jj][2];
			int i2=limite[ii][jj][3];
			int j2=limite[ii][jj][0];
			respf+=checa(i, j, i2, j2);
		}
	}

	return respf;
}

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