제출 #1008787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008787		PagodePaiva	Rectangles (IOI19_rect)	C++17	0 / 100	10 ms	23388 KiB

rect

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

using namespace std;

const int N = 2510;
const int inf = N;
const int LOGN = 12;

int32_t v[N][N];
int p1[N][N];
int p2[N][N];
int p3[N][N];
int p4[N][N];
int lg2[N];

int logg2(int x){
	return lg2[x];
}

struct RMQmin{
	int val[N][LOGN];
	int n;
	void build(vector <int> v){
		n = v.size();
		for(int i = 1;i <= n;i++){
			val[i][0] = v[i-1];
		}
		for(int j = 1;j < LOGN;j++){
			for(int i = 1;i <= n;i++){
				if((i+(1<< (j-1))) > n) val[i][j] = val[i][j-1];
				else val[i][j] = min(val[i][j-1], val[(i+(1 << (j-1)))][j-1]);
			}
		}
		return;
	}
	int query(int l, int r){
		int t = logg2(r-l+1);
		return min(val[l][t], val[(r-(1<<t)+1)][t]);
	}
} seg1[N], seg3[N];

struct RMQmax{
	int val[N][LOGN];
	int n;
	void build(vector <int> v){
		n = v.size();
		for(int i = 1;i <= n;i++){
			val[i][0] = v[i-1];
		}
		for(int j = 1;j < LOGN;j++){
			for(int i = 1;i <= n;i++){
				if((i+(1<< (j-1))) > n) val[i][j] = val[i][j-1];
				else val[i][j] = max(val[i][j-1], val[i+(1 << (j-1))][j-1]);
			}
		}
		return;
	}
	int query(int l, int r){
		int t = logg2(r-l+1);
		return max(val[l][t], val[r-(1<<t)+1][t]);
	}
} seg2[N], seg4[N];

set <int> s;
int n, m;

bool check(int r1, int c1, int r2, int c2){
	if(r1 == 0 or r2 == n+1 or r2-r1 <= 1) return false;
	if(c1 == 0 or c2 == m+1 or c2-c1 <= 1) return false;
	if(r1+1 > r2-1 or c1+1 > c2-1) return false;
	if(c1 <= 0 or c1 > m or c2 <= 0 or c2 > m or r1 <= 0 or r1 > n or r2 <= 0 or r2 > n) return false;
	int x1 = seg1[c1].query(r1+1, r2-1);
	if(c1+1 <= x1 and x1 <= c2-1) return false;
	x1 = seg2[c2].query(r1+1, r2-1);
	if(c1 < x1 and x1 < c2) return false;
	int x2 = seg3[r1].query(c1+1, c2-1);
	if(r1 < x2 and x2 < r2) return false;
	x2 = seg4[r2].query(c1+1, c2-1);
	if(r1 < x2 and x2 < r2) return false;
	if(s.find(r1+c1*N+r2*N*N+c2*N*N*N) != s.end()) return false;
	s.insert(r1+c1*N+r2*N*N+c2*N*N*N);
	return true;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	lg2[0] = 0;
	lg2[1] = 0;
	for(int i = 2;i < N;i++){
		int t = i/2;
		lg2[i] = lg2[t]+1;
	}
	n = a.size(), m = a[0].size();
	s.clear();
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			v[i][j] = a[i-1][j-1];
		}
	}
	for(int i = 1;i <= n;i++){
		stack <int> s;
		for(int j = 1;j <= m;j++){
			if(s.empty()) s.push(j);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[i][t]){
						p1[i][t] = j;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(j);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p1[i][t] = m+1;
			s.pop();
		}
	}
	for(int i = 1;i <= n;i++){
		stack <int> s;
		for(int j = m;j > 0;j--){
			if(s.empty()) s.push(j);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[i][t]){
						p2[i][t] = j;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(j);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p2[i][t] = 0;
			s.pop();
		}
	}
	for(int j = 1;j <= m;j++){
		stack <int> s;
		for(int i = 1;i <= n;i++){
			if(s.empty()) s.push(i);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[t][j]){
						p3[t][j] = i;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(i);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p3[t][j] = n+1;
			s.pop();
		}
	}
	for(int j = 1;j <= m;j++){
		stack <int> s;
		for(int i = n;i > 0;i--){
			if(s.empty()) s.push(i);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[t][j]){
						p4[t][j] = i;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(i);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p4[t][j] = 0;
			s.pop();
		}
	}
	for(int i = 1;i <= n;i++){
		vector <int> aux1, aux2;
		for(int j = 1;j <= m;j++){
			aux1.push_back(p3[i][j]);
			aux2.push_back(p4[i][j]);
		}
		seg3[i].build(aux1);
		seg4[i].build(aux2);
	}
	for(int j = 1;j <= m;j++){
		vector <int> aux1, aux2;
		for(int i = 1;i <= n;i++){
			aux1.push_back(p1[i][j]);
			aux2.push_back(p2[i][j]);
		}
		seg1[j].build(aux1);
		seg2[j].build(aux2);
	}
	for(int r1 = 1;r1 < n;r1++){
		for(int c1 = 1;c1 < m;c1++){
			int r2 = p3[r1][c1+1];
			int c2 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg1[c1].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
			c2 = p1[r1+1][c1];
			r2 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg3[r1].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
		}
	}
	for(int r1 = 1;r1 < n;r1++){
		for(int c2 = m;c2 > 1;c2--){
			int c1 = p2[r1+1][c2];
			int r2 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg3[r1].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
			r2 = p3[r1][c2-1];
			c1 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg2[c2].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
		}
	}
	for(int r2 = n;r2 > 1;r2--){
		for(int c1 = 1;c1 < m;c1++){
			int r1 = p4[r2][c1+1];
			int c2 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg1[c1].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
			c2 = p1[r2-1][c1];
			r1 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg4[r2].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
			/*
			int c2 = p1[r2-1][c1];
			int r1 = p4[r2][c1+1];
			check(r1, c1, r2, c2);
			*/
		}
	}
	for(int r2 = n;r2 > 1;r2--){
		for(int c2 = m;c2 > 1;c2--){
			int c1 = p2[r2-1][c2];
			int r1 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg4[r2].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
			r1 = p4[r2][c2-1];
			c1 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg2[c2].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
			/*
			int c1 = p2[r2-1][c2];
			int r1 = p4[r2][c2-1];
			check(r1, c1, r2, c2);
			*/
		}
	}
	long long res = s.size();
	return res;
}

• 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