Submission #1064636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1064636	2024-08-18T15:56:13 Z	jamjanek	Rectangles (IOI19_rect)	C++14	10 / 100	6 ms	4444 KB

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]!=m && nast[i][j][2]!=-1 && nast[i][j][3]!=n){
				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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	500 KB	Output is correct
9	Incorrect	1 ms	604 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	500 KB	Output is correct
9	Incorrect	1 ms	604 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	500 KB	Output is correct
9	Incorrect	1 ms	604 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	500 KB	Output is correct
9	Incorrect	1 ms	604 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	860 KB	Output is correct
2	Correct	4 ms	916 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	2 ms	2776 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	2 ms	2648 KB	Output is correct
10	Correct	0 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	500 KB	Output is correct
9	Incorrect	1 ms	604 KB	Output isn't correct
10	Halted	0 ms	0 KB	-