oj.uz

Submission #1064626

# Submission time Handle Problem Language Result Execution time Memory
1064626 2024-08-18T15:52:05 Z jamjanek Rectangles (IOI19_rect) C++14
0 / 100
 6 ms 4444 KB 
#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.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2908 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Incorrect 1 ms 856 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 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 4444 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -