oj.uz

답안 #1054497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1054497 2024-08-12T10:18:32 Z mychecksedad Rectangles (IOI19_rect) C++17
23 / 100
 1130 ms 785424 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
// #define ll long long
#define pb push_back
#define ff first
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ss second
#define int short 
const int N = 2600, K = 20;




long long count_rectangles(std::vector<std::vector<int32_t> > a) {
	int n = a.size();
	int m = a[0].size();
	if(n < 3 || m < 3){
		return 0;
	}

	long long 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 = 1; i + 1 < n; ++i){
		for(int j = 1; j + 1 < m; ++j){
			int l = L[i][j], r = R[i][j];
			while(l > -1 && r < m){
				// cout << i << ' ' << j << ' ' << l + 1 << ' ' << r - 1 << '\n';
				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 = 1; j + 1 < m; ++j){
		for(int i = 1; i + 1 < n; ++i){
			int l = U[i][j], r = D[i][j];
			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];
				}	
			}
		}
	}
// 	for(int i = 0; i < n; ++i){
// 		for(int j = 0; j < m; ++j) cout << L[i][j] << ' ';en;
// 	}

// en;en;
	
// 	for(int i = 0; i < n; ++i){
// 		for(int j = 0; j < m; ++j) cout << R[i][j] << ' ';en;
// 	}
// en;en;

// 	for(int i = 0; i < n; ++i){
// 		for(int j = 0; j < m; ++j) cout << U[i][j] << ' ';en;
// 	}
// en;en;

// 	for(int i = 0; i < n; ++i){
// 		for(int j = 0; j < m; ++j) cout << D[i][j] << ' ';en;
// 	}

	vector<vector<vector<int>>> colranges(max(n,m), vector<vector<int>>(max(n,m)));
	vector<vector<vector<int>>> rowranges(max(n,m), vector<vector<int>>(max(n,m)));
	// cout << "wtf" << endl;
	for(int i = 1; i + 1 < n; ++i){
		for(int j = 1; j + 1 < m; ++j){
			sort(all(rangesL[i][j]), greater<int>());
			rangesL[i][j].erase(unique(all(rangesL[i][j])), rangesL[i][j].end());
			sort(all(rangesU[i][j]), greater<int>());
			rangesU[i][j].erase(unique(all(rangesU[i][j])), rangesU[i][j].end());

			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){
				if(colranges[j][rangesL[i][j][x]].size() && colranges[j][rangesL[i][j][x]].back() < i - 1){
					colranges[j][rangesL[i][j][x]].clear();
				}
				colranges[j][rangesL[i][j][x]].pb(i);
				// cout << rangesL[i][j][x] << ' '; 
			}
			// cout << "R: ";
			for(int x = 0; x < us; ++x){
				if(rowranges[i][rangesU[i][j][x]].size() && rowranges[i][rangesU[i][j][x]].back() < j - 1){
					rowranges[i][rangesU[i][j][x]].clear();
				}
				rowranges[i][rangesU[i][j][x]].pb(j);
				// cout << rangesU[i][j][x] << ' ';
			}
			// en;en;

			for(int y = 0; y < us; ++y){
				int u = rangesU[i][j][y];
				for(int x = 0; x < ls; ++x){
					int l = rangesL[i][j][x];
				
					// cout << i << ' ' << j << ' ' << u << ' ' << l << '\n';
					// cout << (rowranges[i][u].size() >= j - l + 1 && rowranges[i][u][int(rowranges[i][u].size()) - (j - l + 1)] == l) << ' ' <<
					// (colranges[j][l].size() >= i - u + 1 && colranges[j][l][int(colranges[j][l].size()) - (i - u + 1)] == u) << '\n';
					if(rowranges[i][u].size() >= j - l + 1
						&& colranges[j][l].size() >= i - u + 1){
						++ans;
					}else break;
				}
			}
		}
	}


	return ans;
}

Compilation message

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

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 301296 KB Output is correct
2 Correct 148 ms 217260 KB Output is correct
3 Correct 107 ms 294512 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 116 ms 294616 KB Output is correct
6 Correct 108 ms 294628 KB Output is correct
7 Correct 110 ms 294736 KB Output is correct
8 Correct 107 ms 294740 KB Output is correct
9 Correct 110 ms 294624 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 556 ms 478844 KB Output is correct
3 Correct 1105 ms 782984 KB Output is correct
4 Correct 1130 ms 785240 KB Output is correct
5 Correct 1114 ms 785424 KB Output is correct
6 Correct 279 ms 487504 KB Output is correct
7 Correct 449 ms 662100 KB Output is correct
8 Correct 485 ms 686228 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -