제출 #151592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151592		mieszko11b	Rectangles (IOI19_rect)	C++14	100 / 100	4658 ms	974168 KiB

rect

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

using namespace std;

struct rect {
	int x1, x2, y1, y2;
	bool ok;
	
	rect() {};
	rect(int x1, int x2, int y1, int y2) {
		this->x1 = x1;
		this->x2 = x2;
		this->y1 = y1;
		this->y2 = y2;
		this->ok = true;
	}
};

bool operator<(const rect &a, const rect &b) {
	return make_tuple(a.x1, a.x2, a.y1, a.y2) < make_tuple(b.x1, b.x2, b.y1, b.y2);
}

bool operator==(const rect &a, const rect &b) {
	return make_tuple(a.x1, a.x2, a.y1, a.y2) == make_tuple(b.x1, b.x2, b.y1, b.y2);
}

int n, m;
int A[2507][2507], newA[2507][2507];
int L[2507][2507], R[2507][2507], U[2507][2507], D[2507][2507];
int LM[20][2507][2507];
int cnt[2507];
int ok_pow[2507];
vector<rect> candidates;

bool less_op(int a, int b) {
	return a < b;
}

bool less_equal_op(int a, int b) {
	return a <= b;
}

inline bool okx(int x) {
	return x >= 1 && x <= n;
}

inline bool oky(int y) {
	return y >= 1 && y <= m;
}

void calc_firsts(bool (*op)(int, int) ) {
	for(int x = 1 ; x <= n ; x++) {
		stack<int> S;
		for(int y = 1 ; y <= m ; y++) {
			while(!S.empty() && op(A[x][S.top()], A[x][y]))
				S.pop();
			if(S.empty())
				L[x][y] = 0;
			else
				L[x][y] = S.top();
			S.push(y);
		}
	}
	
	for(int x = 1 ; x <= n ; x++) {
		stack<int> S;
		for(int y = m ; y >= 1 ; y--) {
			while(!S.empty() && op(A[x][S.top()], A[x][y]))
				S.pop();
			if(S.empty())
				R[x][y] = m + 1;
			else
				R[x][y] = S.top();
			S.push(y);
		}
	}
	
	for(int y = 1 ; y <= m ; y++) {
		stack<int> S;
		for(int x = 1 ; x <= n ; x++) {
			while(!S.empty() && op(A[S.top()][y], A[x][y]))
				S.pop();
			if(S.empty())
				U[x][y] = 0;
			else
				U[x][y] = S.top();
			S.push(x);
		}
	}

	for(int y = 1 ; y <= m ; y++) {
		stack<int> S;
		for(int x = n ; x >= 1 ; x--) {
			while(!S.empty() && op(A[S.top()][y], A[x][y]))
				S.pop();
			if(S.empty())
				D[x][y] = n + 1;
			else
				D[x][y] = S.top();
			S.push(x);
		}
	}
}

void find_candidates() {
	for(int x = 1 ; x <= n ; x++) {
		for(int y = 1 ; y <= m ; y++) {
			int x1 = U[x][y];
			int x2 = D[x][y];
			int y1 = L[x][y];
			int y2 = R[x][y];
			
			if(okx(x1) && okx(x2) && oky(y1) && oky(y2) && x1 + 1 < x2 && y1 + 1 < y2)
				candidates.emplace_back(x1 + 1, x2 - 1, y1 + 1, y2 - 1);
		}
	}
}

int maxv(int x1, int x2, int y) {
	int p = ok_pow[x2 - x1 + 1];
	return max(LM[p][x1][y], LM[p][x2 - (1 << p) + 1][y]);
}

void calc_left() {
	for(int x = 1 ; x <= n ; x++) {
		stack<int> S;
		for(int y = 1 ; y <= m ; y++) {
			while(!S.empty() && A[x][S.top()] < A[x][y])
				S.pop();
			if(S.empty())
				LM[0][x][y] = L[x][y] = 0;
			else
				LM[0][x][y] = L[x][y] = S.top();
			S.push(y);
		}
	}
	
	for(int k = 1 ; k < 20 ; k++)
		for(int x = 1 ; x <= n ; x++)
			for(int y = 1 ; y <= m ; y++)
				LM[k][x][y] = max(LM[k - 1][x][y], okx(x + (1 << (k - 1))) ? LM[k - 1][x + (1 << (k - 1))][y] : 0);
}

void one_check() {
	calc_left();
	for(rect &r : candidates) {
		if(maxv(r.x1, r.x2, r.y2 + 1) >= r.y1)
			r.ok = false;
	}
}

void mirror_swap() {
	for(int x = 1 ; x <= n ; x++)
		reverse(A[x] + 1, A[x] + m + 1);
	for(rect &r : candidates) {
		swap(r.y1, r.y2);
		r.y1 = m - r.y1 + 1;
		r.y2 = m - r.y2 + 1;
	}
}

void swap_dim() {
	for(int x = 1 ; x <= n ; x++)
		for(int y = 1 ; y <= m ; y++)
			newA[y][x] = A[x][y];
			
	for(int x = 1 ; x <= n ; x++)
		for(int y = 1 ; y <= m ; y++)
			A[y][x] = newA[y][x];
			
	for(rect &r : candidates) {
		swap(r.x1, r.y1);
		swap(r.x2, r.y2);
	}
			
	swap(n, m);
}

int count() {
	int res = 0;
	for(rect r : candidates)
		if(r.ok)
			res++;
			
	return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	
	int pot = 0;
	for(int i = 1 ; i <= max(n, m) ; i++) {
		if((1 << (pot+1)) <= i)
			pot++;
		ok_pow[i] = pot;
	}
	
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < m ; j++)
			A[i + 1][j + 1] = a[i][j];
			
	calc_firsts(less_equal_op);
	find_candidates();
	
	//sort(candidates.begin(), candidates.end());
	
	vector<rect> ncand;
	int smaller;
	
	memset(cnt, 0, sizeof cnt);
	for(rect r : candidates)
		cnt[r.x1]++;
	smaller = 0;
	for(int i = 0 ; i < 2507 ; i++) {
		int d = cnt[i];
		cnt[i] = smaller;
		smaller += d;
	}
	ncand.resize(candidates.size());
	for(rect r : candidates)
		ncand[cnt[r.x1]++] = r;
	swap(ncand, candidates);
	
	memset(cnt, 0, sizeof cnt);
	for(rect r : candidates)
		cnt[r.x2]++;
	smaller = 0;
	for(int i = 0 ; i < 2507 ; i++) {
		int d = cnt[i];
		cnt[i] = smaller;
		smaller += d;
	}
	ncand.resize(candidates.size());
	for(rect r : candidates)
		ncand[cnt[r.x2]++] = r;
	swap(ncand, candidates);
	
	memset(cnt, 0, sizeof cnt);
	for(rect r : candidates)
		cnt[r.y1]++;
	smaller = 0;
	for(int i = 0 ; i < 2507 ; i++) {
		int d = cnt[i];
		cnt[i] = smaller;
		smaller += d;
	}
	ncand.resize(candidates.size());
	for(rect r : candidates)
		ncand[cnt[r.y1]++] = r;
	swap(ncand, candidates);
	
	memset(cnt, 0, sizeof cnt);
	for(rect r : candidates)
		cnt[r.y2]++;
	smaller = 0;
	for(int i = 0 ; i < 2507 ; i++) {
		int d = cnt[i];
		cnt[i] = smaller;
		smaller += d;
	}
	ncand.resize(candidates.size());
	for(rect r : candidates)
		ncand[cnt[r.y2]++] = r;
	swap(ncand, candidates);
	
	candidates.resize(distance(candidates.begin(), unique(candidates.begin(), candidates.end())));
	
	one_check();
	
	//cout << count() << endl;
	mirror_swap();
	one_check();
	//cout << count() << endl;
	swap_dim();

	one_check();
	//cout << count() << endl;
	mirror_swap();
	one_check();
			
	return count();
}

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