Submission #1064626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064626		jamjanek	Rectangles (IOI19_rect)	C++14	0 / 100	6 ms	4444 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>stosy[2510];
int nast[2510][2510][4];

int maxi1(int war, int l, int r){
	int res = -1;
	for(int i=l;i<=r;i++)
		res = max(res, nast[i][war][0]);
	return res;
}
int mini1(int war, int l, int r){
	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast[i][war][1]);
	return res;
}
int maxi2(int war, int l, int r){
	int res = -1;
	for(int i=l;i<=r;i++)
		res = max(res, nast[war][i][2]);
	return res;
}
int mini2(int war, int l, int r){
	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast[war][i][3]);
	return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	int i, j;

	//poprzednie po x [0]	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][0] = stosy[i].back().second;
			else
				nast[i][j][0] = -1;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();

	//nastepne po x [1]

	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][1] = stosy[i].back().second;
			else
				nast[i][j][1] = m;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();
	
	//poprzednie po y [2]
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][2] = stosy[i].back().second;
			else
				nast[j][i][2] = -1;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	//nastepne po y [3]
	for(i=0;i<m;i++){
		for(j = n-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][3] = stosy[i].back().second;
			else
				nast[j][i][3] = n;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	set<pair<pair<int,int>, pair<int,int>>>sett;
	for(i=1;i<n-1;i++)
		for(j=1;j<m-1;j++)
			if(nast[i][j][0]!=-1 && nast[i][j][1]!=n && nast[i][j][2]!=-1 && nast[i][j][3]!=-1){
				sett.insert({{nast[i][j][0], nast[i][j][1]}, {nast[i][j][2], nast[i][j][3]}});
			}
	long long wynik = 0;
	for(auto x: sett){
		if(mini1(x.first.first, x.second.first+1, x.second.second-1)<x.first.second)continue;
		if(maxi1(x.first.second, x.second.first+1, x.second.second-1)>x.first.first)continue;

		if(mini2(x.second.first, x.first.first+1, x.first.second-1)<x.second.second)continue;
		if(maxi2(x.second.second, x.first.first+1, x.first.second-1)>x.second.first)continue;
		wynik++;
	}
	
	return wynik;
}

• 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