Submission #1160723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160723		hyakup	Rectangles (IOI19_rect)	C++20	27 / 100	1154 ms	92656 KiB

rect

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

const int inf = 1e9 + 10;
const int maxn = 200 + 10;
const int logn = 10;

struct Node{
	int l, r, u, d; Node( int l = -inf, int r = inf, int u = -inf, int d = inf ) : l(l), r(r), u(u), d(d) {}
	Node operator + ( Node n ){
		return Node( min( l, n.l ), max( r, n.r ), min( u, n.u ), max( d, n.d ) );
	}
};

Node dp[logn][logn][maxn][maxn];


int l[maxn][maxn], r[maxn][maxn], u[maxn][maxn], d[maxn][maxn];

long long count_rectangles( vector<vector<int>> mat ) {
	int n = mat.size(), m = mat[0].size();

	for( int i = 0; i < n; i++ ){
		stack<pair<int, pair<int, int>>> pilha;
		pilha.push({ inf, make_pair(-1, -1) });
		for( int j = 0; j < m; j++ ){
			l[i][j] = -1; r[i][j] = m;
			while( pilha.top().first < mat[i][j] ){
				auto [a, b] = pilha.top().second;
				r[a][b] = j;
				pilha.pop();
			}
			auto [a, b] = pilha.top().second;
			l[i][j] = (( pilha.top().first == mat[i][j] ) ? l[a][b] : b );
			pilha.push({ mat[i][j], make_pair( i, j ) });

		}
	}

	for( int j = 0; j < m; j++ ){
		stack<pair<int, pair<int, int>>> pilha;
		pilha.push({ inf, make_pair(-1, -1) });
		for( int i = 0; i < n; i++ ){
			u[i][j] = -1; d[i][j] = n;
			while( pilha.top().first < mat[i][j] ){
				auto [a, b] = pilha.top().second;
				d[a][b] = i;
				pilha.pop();
			}
			auto [a, b] = pilha.top().second;
			u[i][j] = (( pilha.top().first == mat[i][j] ) ? u[a][b] : a );
			pilha.push({ mat[i][j], make_pair( i, j ) });
		}
	}


  for( int ki = 0; ki < logn; ki++ )
    for( int kj = 0; kj < logn; kj++ )
      for( int i = 0; i < n; i++ )
        for( int j = 0; j < m; j++ ){
          if( ki == 0 && kj == 0) dp[0][0][i][j] = Node( l[i][j], r[i][j], u[i][j], d[i][j] );
          else if( ki == 0 ){
            if( j + (1<<kj) <= m ) dp[ki][kj][i][j] = dp[ki][kj - 1][i][j] + dp[ki][kj - 1][i][j + (1<<(kj - 1))];
          }
          else if( i + (1<<ki) <= n ) dp[ki][kj][i][j] = dp[ki - 1][kj][i][j] + dp[ki - 1][kj][i + (1<<(ki - 1))][j];
        }

  auto query = [&]( int i1, int j1, int i2, int j2 ){
    int ki = 31 - __builtin_clz(i2 - i1 + 1), kj = 31 - __builtin_clz(j2 - j1 + 1);
    return dp[ki][kj][i1][j1] + dp[ki][kj][i1][j2 - (1<<kj) + 1] + dp[ki][kj][i2 - (1<<ki) + 1][j1] + dp[ki][kj][i2 - (1<<ki) + 1][j2 - (1<<kj) + 1];
  };

	ll resp = 0;

  Node x = query( 1, 1, 1, 1 );

  set<tuple<int, int, int, int>> s;

  for( int i = 1; i < n - 1; i++ )
    for( int j = 1; j < m - 1; j++ ){
      if( l[i][j] == -1 || r[i][j] == m || u[i][j] == -1 || d[i][j] == n ) continue;
      Node x = query( u[i][j] + 1, l[i][j] + 1, d[i][j] - 1, r[i][j] - 1 );
      if( x.u < u[i][j] || x.l < l[i][j] || x.d > d[i][j] || x.r > r[i][j] ) continue;
      s.insert(make_tuple( l[i][j], r[i][j], u[i][j], d[i][j] ) );
    }

  if( resp > n*m ) return 0;

	return s.size();
}

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