제출 #1160692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160692		hyakup	Rectangles (IOI19_rect)	C++20	10 / 100	197 ms	402328 KiB

rect

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

const int inf = 1e9 + 10;
const int maxn = 2500 + 10;

class Segment_Tree{
	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( max( l, n.l ), min( r, n.r ), max( u, n.u ), min( d, n.d ) );
		}
	};
	vector<Node> seg;

	int n;

	void update( int pos, int ini, int fim, int id, Node novo ){
		if( ini > id || id > fim ) return;
		if( ini == fim ){ seg[pos] = novo; return; }
		int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
		update( l, ini, mid, id, novo ); update( r, mid + 1, fim, id, novo );
		seg[pos] = seg[l] + seg[r];
	}

	Node query( int pos, int ini, int fim, int ki, int kf ){
		if( ki > fim || ini > kf ) return seg[0];
		if( ki <= ini && fim <= kf ) return seg[pos];
		int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
		return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
	}

public:

	void update( int id, int l, int r, int u, int d ){
		update( 1, 0, n, id, Node( l, r, u, d ) );
	}

	int query( int l, int r, int t ){
		Node x = query( 1, 0, n, l, r );

		if( t == 0 ) return x.u;
		if( t == 1 ) return x.r;
		if( t == 2 ) return x.d;
		return x.l;
	}

	Segment_Tree() : n(maxn) { seg.resize(4*maxn); }
};

int bit[maxn][maxn], 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();

	vector<tuple<int, int, int>> ordem;

	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 ) });


			ordem.emplace_back( mat[i][j], 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 ) });
		}
	}

	sort( ordem.begin(), ordem.end() );
	vector<Segment_Tree> linha( n ), coluna( m );

	auto update = [&]( int a, int b, int val ){
		a++; b++;
		for( int i = a; i < maxn; i += i&-i )
			for( int j = b; j < maxn; j += j&-j ) bit[i][j] += val;
	};

	auto query = [&]( int a, int b ){
		a++; b++;
		int sum = 0;
		for( int i = a; i > 0; i -= i&-i )
			for( int j = b; j > 0; j -= j&-j ) sum += bit[i][j];
		return sum;
	};

	auto cont = [&]( int i1, int j1, int i2, int j2 ){
		return query( i2, j2 ) - query( i2, j1 - 1 ) - query( i1 - 1, j2 ) + query( i1 - 1, j1 - 1 );
	};

	int resp = 0;

	for( auto [val, i, j] : ordem ){
		linha[i].update( j, l[i][j], r[i][j], u[i][j], d[i][j] );
		coluna[j].update( i, l[i][j], r[i][j], u[i][j], d[i][j] );

		update( i, j, 1 );

		if( l[i][j] == -1 || r[i][j] == m || u[i][j] == -1 || d[i][j] == n ) continue;
		int area = ( d[i][j] - u[i][j] - 1 )*( r[i][j] - l[i][j] - 1 );
		if( cont( u[i][j] + 1, l[i][j] + 1, d[i][j] - 1, r[i][j] - 1 ) != area ) continue;

		if( linha[u[i][j]].query( l[i][j] + 1, r[i][j] - 1, 2) < d[i][j] ) continue;
		if( linha[d[i][j]].query( l[i][j] + 1, r[i][j] - 1, 0) > u[i][j] ) continue;

		if( coluna[l[i][j]].query( u[i][j] + 1, d[i][j] - 1, 1) < r[i][j] ) continue;
		if( coluna[r[i][j]].query( u[i][j] + 1, d[i][j] - 1, 3) > l[i][j] ) continue;

		resp++;
	}

	return resp;
}

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