Submission #292559

#	Time	Username	Problem	Language	Result	Execution time	Memory
292559		miss_robot	Rectangles (IOI19_rect)	C++14	50 / 100	5052 ms	632568 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

#pragma GCC optimize("O3")

using namespace std;

const int N = 2500, M = 2500, L = 1024;
int n, m;
long long sol;
int f[N][M], dx[]={0,1,0,-1}, dy[]={1,0,-1,0}, up[N][2*L], dwn[N][2*L], lft[M][2*L], rgt[M][2*L];

int qry(int a, int b, int t[]){
	a += L, b += L;
	int r = 7e6;
	while(a <= b){
		if(a&1) r = min(r, t[a++]);
		if(!(b&1)) r = min(r, t[b--]);
		a >>= 1, b >>= 1;
	}
	return r;
}

void st1(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int k = j+1; k < m; k++){
				if(f[i][k] < f[i][j]) rgt[j][i+L]++;
				else break;
			}
			for(int k = j-1; k >= 0; k--){
				if(f[i][k] < f[i][j]) lft[j][i+L]++;
				else break;
			}
			for(int k = i+1; k < n; k++){
				if(f[k][j] < f[i][j]) dwn[i][j+L]++;
				else break;
			}
			for(int k = i-1; k >= 0; k--){
				if(f[k][j] < f[i][j]) up[i][j+L]++;
				else break;
			}
		}
	}
	for(int i = 0; i < n; i++)
		for(int j = L-1; j; j--)
			up[i][j] = min(up[i][j<<1], up[i][(j<<1)|1]),
			dwn[i][j] = min(dwn[i][j<<1], dwn[i][(j<<1)|1]);
	for(int j = 0; j < m; j++)
		for(int i = L-1; i; i--)
			lft[j][i] = min(lft[j][i<<1], lft[j][(i<<1)|1]),
			rgt[j][i] = min(rgt[j][i<<1], rgt[j][(i<<1)|1]);
	for(int x = 0; x < n-2; x++){
		for(int y = 1; y < m-1; y++){
			for(int Y = y; Y < m-1; Y++){
				int mxlen = qry(y, Y, dwn[x]);
				for(int X = x+1; X-x <= mxlen && X < n-1; X++){
					if(qry(x+1, X, rgt[y-1]) < Y-y+1
						|| qry(x+1, X, lft[Y+1]) < Y-y+1) break;
					if(qry(y, Y, up[X+1]) >= X-x) sol++;
				}
			}
		}
	}
}

void st5(){
	for(int i = 1, mx; i < m-1; i++){
		mx = 0;
		for(int j = i; j < m-1; j++){
			mx = max(mx, f[1][j]);
			if(f[1][j] >= f[1][i-1] || f[1][j] >= f[0][j] || f[1][j] >= f[2][j]) break;
			if(mx < f[1][j+1]) sol++;
		}
	}
}

int vis[N][M];

void flood(int x, int y, int &maxx, int &maxy, int &minx, int &miny, int &c){
	if(x < 0 || y < 0 || x == n || y == m || vis[x][y] || f[x][y]) return;
	c++;
	vis[x][y] = 1;
	maxx = max(maxx, x), minx = min(minx, x);
	maxy = max(maxy, y), miny = min(miny, y);
	for(int k = 0, i, j; k < 4; k++){
		i = x+dx[k], j = y+dy[k];
		flood(i, j, maxx, maxy, minx, miny, c);
	}
}

void st6(){
	for(int i = 1; i < n-1; i++){
		for(int j = 1; j < m-1; j++){
			if(vis[i][j] || f[i][j]) continue;
			int maxx = i, minx = i, maxy = j, miny = j, c = 0;
			flood(i, j, maxx, maxy, minx, miny, c);
			if(minx && miny && maxx < n-1 && maxy < m-1 && c == (maxx-minx+1)*(maxy-miny+1)) sol++;
		}
	}
}

long long count_rectangles(vector< vector<int> > a){
	n = a.size(), m = a[0].size();
	if(n < 3 || m < 3) return 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			f[i][j] = a[i][j];
	int s6 = 1;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(f[i][j] > 1) s6 = 0;
	if(n == 3) st5();
	else if(s6) st6();
	else st1();
	return sol;
}

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