제출 #425144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425144		alireza_kaviani	Rectangles (IOI19_rect)	C++14	0 / 100	517 ms	295576 KiB

rect

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

typedef long long ll;
typedef pair<int, int> pii;

#define SZ(x)		int((x).size())
#define sep			' '

const int MAXN = 2510;
const int MOD = 1e9 + 7;

int n , m , L[MAXN][MAXN] , R[MAXN][MAXN];
vector<int> vec[MAXN][MAXN];

int solve(int x , int y , int l , int r){
	vector<pii> ans;
	for(int i = l ; i <= r ; i++){
		if(l <= L[x + 1][i] && L[x + 1][i] + 1 != i)	ans.push_back({L[x + 1][i] , i});
		if(R[x + 1][i] <= r && i + 1 != R[x + 1][i])	ans.push_back({i , R[x + 1][i]});
	}
	for(int i = x + 2 ; i < y ; i++){
		vector<pii> cur;
		for(pii j : ans){
			int a = j.first , b = j.second;
			if(R[i][a] == b || L[i][b] == a)	cur.push_back(j);
		}
		ans = cur;
	}
//	cout << x << sep << y << sep << l << sep << r << sep << SZ(ans) << endl;
	return SZ(ans);
}

ll count_rectangles(vector<vector<int>> a) {
	for(int i = 0 ; i < MAXN ; i++){
		fill(L[i] , L[i] + MAXN , -1);
		fill(R[i] , R[i] + MAXN , MOD);
	}
	n = SZ(a) , m = SZ(a[0]); ll ans = 0;
	for(int i = 1 ; i + 1 < n ; i++){
		vector<int> stk;
		for(int j = 0 ; j < m ; j++){
			while(SZ(stk) && a[i][j] >= a[i][stk.back()]){
				vec[stk.back()][j].push_back(i);
				stk.pop_back();
			}
			if(SZ(stk))	vec[stk.back()][j].push_back(i);
			stk.push_back(j);
		}
	}
	for(int i = 0 ; i < m ; i++){
		vector<int> stk;
		for(int j = 0 ; j < n ; j++){
			while(SZ(stk) && a[j][i] >= a[stk.back()][i]){
				R[i][stk.back()] = j;
				stk.pop_back();
			}
			if(SZ(stk))	L[i][j] = stk.back();
			stk.push_back(j);
		}
	}
	for(int i = 0 ; i < m ; i++){
		for(int j = i + 2 ; j < m ; j++){
			vec[i][j].push_back(MOD);
			int first = -1;
			for(int k = 0 ; k < SZ(vec[i][j]) ; k++){
				if(k == 0 || vec[i][j][k] != vec[i][j][k - 1] + 1){
					if(first != -1)	ans += solve(i , j , first - 1 , vec[i][j][k - 1] + 1);
					first = vec[i][j][k];
				}
			}
		}
	}

	return ans;
}

• 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