Submission #425151

#	Time	Username	Problem	Language	Result	Execution time	Memory
425151		alireza_kaviani	Rectangles (IOI19_rect)	C++14	72 / 100	5046 ms	394420 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++){
			int flag = 0;
			while(SZ(stk) && a[i][j] >= a[i][stk.back()]){
				vec[stk.back()][j].push_back(i);
				if(a[i][j] == a[i][stk.back()])	flag = 1;
//				cout << stk.back() << sep << j << sep << i << endl;
				stk.pop_back();
			}
			if(SZ(stk) && flag == 0)	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++){
			int flag = 0;
			while(SZ(stk) && a[j][i] >= a[stk.back()][i]){
				R[i][stk.back()] = j;
				if(a[j][i] == a[stk.back()][i])	flag = 1;
				stk.pop_back();
			}
			if(SZ(stk) && flag == 0)	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: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28