oj.uz

Submission #1051696

# Submission time Handle Problem Language Result Execution time Memory
1051696 2024-08-10T09:05:45 Z mychecksedad Rectangles (IOI19_rect) C++17
0 / 100
 514 ms 734484 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ff first
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ss second
const int N = 2600, K = 20;




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

	if(n < 3 || m < 3){
		return 0;
	}

	ll ans = 0;	
	vector<vector<int>> L, R, D, U;
	L.resize(n, vector<int>(m));
	R.resize(n, vector<int>(m));
	D.resize(n, vector<int>(m));
	U.resize(n, vector<int>(m));

	for(int i = 0; i < n; ++i){
		vector<int> q;
		for(int j = 0; j < m; ++j){
			while(!q.empty() && a[i][q.back()] <= a[i][j]) q.pop_back();
			if(q.empty()){
				L[i][j] = -1;
			}else{
				L[i][j] = q.back();
			}
			q.pb(j);
		}
		q.clear();
		for(int j = m - 1; j >= 0; --j){
			while(!q.empty() && a[i][q.back()] <= a[i][j]) q.pop_back();
			if(q.empty()){
				R[i][j] = m;
			}else{
				R[i][j] = q.back();
			}
			q.pb(j);
		}
	}
	for(int j = 0; j < m; ++j){
		vector<int> q;
		for(int i = 0; i < n; ++i){
			while(!q.empty() && a[q.back()][j] <= a[i][j]) q.pop_back();
			if(q.empty()){
				U[i][j] = -1;
			}else{
				U[i][j] = q.back();
			}
			q.pb(i);
		}
		q.clear();
		for(int i = n - 1; i >= 0; --i){
			while(!q.empty() && a[q.back()][j] <= a[i][j]) q.pop_back();
			if(q.empty()){
				D[i][j] = n;
			}else{
				D[i][j] = q.back();
			}
			q.pb(i);
		}
	}

	vector<vector<vector<int>>> rangesL(n, vector<vector<int>>(m));
	vector<vector<vector<int>>> rangesU(n, vector<vector<int>>(m));

	for(int i = 0; i < n; ++i){
		for(int j = 1; j + 1 < m; ++j){
			if(a[i][j - 1] > a[i][j] && a[i][j] < a[i][j + 1]){
				int l = j - 1, r = j + 1;
				while(l > -1 && r < m){
					rangesL[i][r - 1].pb(l + 1);
					if(a[i][l] < a[i][r]){
						l = L[i][l];
					}else if(a[i][l] > a[i][r]){
						r = R[i][r];
					}else{
						l = L[i][l];
						r = R[i][r];
					}
				}
			}
		}
	}
	for(int j = 0; j < m; ++j){
		for(int i = 1; i + 1 < n; ++i){
			if(a[i - 1][j] > a[i][j] && a[i][j] < a[i + 1][j]){
				int l = i - 1, r = i + 1;
				while(l > -1 && r < n){
					// cout << l << ' ' << r << ' ' << i << ' ' << j << '\n';
					rangesU[r - 1][j].pb(l + 1);
					if(a[l][j] < a[r][j]){
						l = U[l][j];
					}else if(a[l][j] > a[r][j]){
						r = D[r][j];
					}else{
						l = U[l][j];
						r = D[r][j];
					}
				}
			}
		}
	}

	vector<vector<vector<int>>> colranges(n, vector<vector<int>>(m));
	vector<vector<vector<int>>> rowranges(n, vector<vector<int>>(m));

	for(int i = 1; i + 1 < n; ++i){
		for(int j = 1; j + 1 < m; ++j){
			sort(all(rangesL[i][j]), greater<int>());
			sort(all(rangesU[i][j]), greater<int>());
			int ls = rangesL[i][j].size();
			int us = rangesU[i][j].size();
			// cout << i << ' ' << j << '\n';
			// cout << "L: ";
			for(int x = 0; x < ls; ++x){
				colranges[j][rangesL[i][j][x]].pb(i);
				// cout << rangesL[i][j][x] << ' '; 
			}
			// cout << "R: ";
			for(int x = 0; x < us; ++x){
				rowranges[i][rangesU[i][j][x]].pb(j);
				// cout << rangesU[i][j][x] << ' ';
			}
			// en;en;
			for(int x = 0; x < ls; ++x){
				int l = rangesL[i][j][x];
				for(int y = 0; y < us; ++y){
					int u = rangesU[i][j][y];
					// cout << i << ' ' << j << ' ' << u << ' ' << l << '\n';
					if(rowranges[i][u].size() >= j - l + 1 && rowranges[i][u][rowranges[i][u].size() - (j - l + 1)] == l
						&& colranges[j][l].size() >= i - u + 1 && colranges[j][l][colranges[j][l].size() - (i - u + 1)] == u){
						++ans;
					}else break;
				}
			}
		}
	}


	return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:142:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  142 |      if(rowranges[i][u].size() >= j - l + 1 && rowranges[i][u][rowranges[i][u].size() - (j - l + 1)] == l
      |         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
rect.cpp:143:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |       && colranges[j][l].size() >= i - u + 1 && colranges[j][l][colranges[j][l].size() - (i - u + 1)] == u){
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2648 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 514 ms 734484 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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