Submission #1193697

#TimeUsernameProblemLanguageResultExecution timeMemory
1193697hyakupRectangles (IOI19_rect)C++20
72 / 100
5062 ms796604 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int inf = 1e9 + 10; const int maxn = 2500; int l[maxn][maxn], r[maxn][maxn], u[maxn][maxn], d[maxn][maxn]; class Segment_Tree{ struct Node{ int v1, v2; Node( int v1 = -inf, int v2 = inf ) : v1(v1), v2(v2) {} Node operator + ( Node n ){ return Node( max( v1, n.v1 ), min( v2, n.v2 ) ); } } seg[4*maxn]; 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 ); } void build( int pos, int ini, int fim, int id, int t ){ if( ini == fim ){ if( t ) seg[pos] = Node( u[id][ini], d[id][ini] ); else seg[pos] = Node( l[ini][id], r[ini][id] ); return; } int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2; build( l, ini, mid, id, t ); build( r, mid + 1, fim, id, t ); seg[pos] = seg[l] + seg[r]; } public: int query( int l, int r, int t ){ Node x = query( 1, 0, maxn - 1, l, r ); return (( t == 0 ) ? x.v1 : x.v2 ); } void build( int id, int t ){ build( 1, 0, maxn - 1, id, t ); } }; Segment_Tree linha[maxn], coluna[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, int>> pilha; pilha.push({ inf, -1 }); for( int j = 0; j < m; j++ ){ l[i][j] = -1; r[i][j] = m; while( pilha.top().first < mat[i][j] ){ r[i][pilha.top().second] = j; pilha.pop(); } l[i][j] = pilha.top().second; pilha.push({ mat[i][j], j }); } for( int j = 0; j < m; j++ ) if( l[i][j] != -1 && mat[i][j] == mat[i][l[i][j]] ) r[i][l[i][j]] = j; } for( int j = 0; j < m; j++ ){ stack<pair<int, int>> pilha; pilha.push({ inf, -1 }); for( int i = 0; i < n; i++ ){ u[i][j] = -1; d[i][j] = n; while( pilha.top().first < mat[i][j] ){ d[pilha.top().second][j] = i; pilha.pop(); } u[i][j] = pilha.top().second; pilha.push({ mat[i][j], i }); } for( int i = 0; i < n; i++ ) if( u[i][j] != -1 && mat[i][j] == mat[u[i][j]][j] ) d[u[i][j]][j] = i; } for( int i = 0; i < n; i++ ) linha[i].build( i, 1 ); for( int j = 0; j < m; j++ ) coluna[j].build( j, 0 ); for( int i = 0; i < n; i++ ) for( int j = 0; j < m; j++ ){ if( l[i][j] != -1 && mat[i][j] == mat[i][l[i][j]] ) l[i][j] = l[i][l[i][j]]; if( u[i][j] != -1 && mat[i][j] == mat[u[i][j]][j] ) u[i][j] = u[u[i][j]][j]; } for( int i = n - 1; i >= 0; i-- ) for( int j = m - 1; j >= 0; j-- ){ if( r[i][j] != m && mat[i][j] == mat[i][r[i][j]] ) r[i][j] = r[i][r[i][j]]; if( d[i][j] != n && mat[i][j] == mat[d[i][j]][j] ) d[i][j] = d[d[i][j]][j]; } 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; if( s.find(make_tuple( l[i][j], r[i][j], u[i][j], d[i][j])) != s.end() ) continue; if( linha[u[i][j]].query( l[i][j] + 1, r[i][j] - 1, 1) < 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, 0) > l[i][j] ) continue; s.insert(make_tuple( l[i][j], r[i][j], u[i][j], d[i][j] )); } return (int)s.size(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...