oj.uz

Submission #1054862

# Submission time Handle Problem Language Result Execution time Memory
1054862 2024-08-12T12:44:49 Z mychecksedad Rectangles (IOI19_rect) C++17
50 / 100
 3288 ms 1048576 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 = 2502, K = 20;

int c = 0, C[100000];
struct Fenwick{
  int n;
  vector<int> t, U;
  Fenwick(int _n){
    n = _n;
    t.resize(n+1, 0);
  }
  void add(int v){
    while(v <= n){
      t[v]++;
      C[c++] = v;
      v += (v&-v);
    }
  }
  int get(int v){
    int res = 0;
    while(v > 0){
      res += t[v];
      v -= (v&-v);
    }
    return res;
  }
  void rollback(){
  	for(int i = 0; i < c; ++i) t[C[i]] = 0;
  	c = 0;
  }
};
 

vector<int> colranges[N][N];
vector<int> rowranges[N][N];
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){
		Fenwick fenw(max(n,m));
		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;
			// Fenwick fenw();
			sort(all(rangesL[i][j]), [&](const int &g, const int &h){
				return colranges[j][g].size() < colranges[j][h].size();
			});
			// sort(all(rangesU[i][j]), [&](const int &g, const int &h){
			// 	return rowranges[i][g].size() > rowranges[i][h].size();
			// });
			int p = ls - 1;
			
			for(int y = us - 1; y >= 0; --y){
				int u = rangesU[i][j][y];
				// if(y < us - 1) assert(rangesU[i][j][y] >= rangesU[i][j][u + 1]);
				int sz = rowranges[i][u].size();

				// if(p != -1) cout << colranges[j][rangesL[i][j][p]].size() << ' ' << i - u + 1 << '\n';

				while(p > -1 && colranges[j][rangesL[i][j][p]].size() >= i - u + 1){
					fenw.add(j - rangesL[i][j][p] + 1);
					// cout << j - rangesL[i][j][p] + 1 << 'f';
					--p;
				}
				ans += fenw.get(sz);
				// cout << sz << ' ' << i << ' ' << j << ' ' << u << ' ' << ans << '\n';

				// for(int x = ls - 1; x >= 0; --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(sz >= j - l + 1
					// 	&& colranges[j][l].size() >= i - u + 1){
					// 	++ans;
					// }
				// }
			}
			fenw.rollback();
		}
	}


	return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:208:59: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  208 |     while(p > -1 && colranges[j][rangesL[i][j][p]].size() >= i - u + 1){
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 294224 KB Output is correct
2 Correct 42 ms 294488 KB Output is correct
3 Correct 43 ms 294484 KB Output is correct
4 Correct 43 ms 294492 KB Output is correct
5 Correct 43 ms 294484 KB Output is correct
6 Correct 44 ms 294480 KB Output is correct
7 Correct 43 ms 294252 KB Output is correct
8 Correct 42 ms 294372 KB Output is correct
9 Correct 43 ms 294492 KB Output is correct
10 Correct 43 ms 294456 KB Output is correct
11 Correct 44 ms 294484 KB Output is correct
12 Correct 43 ms 294344 KB Output is correct
13 Correct 42 ms 294352 KB Output is correct
14 Correct 43 ms 294236 KB Output is correct
15 Correct 43 ms 294236 KB Output is correct
16 Correct 47 ms 294228 KB Output is correct
17 Correct 43 ms 294236 KB Output is correct
18 Correct 43 ms 294224 KB Output is correct
19 Correct 43 ms 294484 KB Output is correct
20 Correct 42 ms 294236 KB Output is correct
21 Correct 41 ms 294224 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 294224 KB Output is correct
2 Correct 42 ms 294488 KB Output is correct
3 Correct 43 ms 294484 KB Output is correct
4 Correct 43 ms 294492 KB Output is correct
5 Correct 43 ms 294484 KB Output is correct
6 Correct 44 ms 294480 KB Output is correct
7 Correct 43 ms 294252 KB Output is correct
8 Correct 42 ms 294372 KB Output is correct
9 Correct 43 ms 294492 KB Output is correct
10 Correct 43 ms 294456 KB Output is correct
11 Correct 44 ms 294484 KB Output is correct
12 Correct 43 ms 294344 KB Output is correct
13 Correct 42 ms 294352 KB Output is correct
14 Correct 43 ms 294236 KB Output is correct
15 Correct 43 ms 294236 KB Output is correct
16 Correct 47 ms 294228 KB Output is correct
17 Correct 43 ms 294236 KB Output is correct
18 Correct 43 ms 294224 KB Output is correct
19 Correct 43 ms 294484 KB Output is correct
20 Correct 42 ms 294236 KB Output is correct
21 Correct 41 ms 294224 KB Output is correct
22 Correct 51 ms 297476 KB Output is correct
23 Correct 52 ms 297316 KB Output is correct
24 Correct 50 ms 297300 KB Output is correct
25 Correct 46 ms 295000 KB Output is correct
26 Correct 45 ms 295248 KB Output is correct
27 Correct 46 ms 295252 KB Output is correct
28 Correct 50 ms 295248 KB Output is correct
29 Correct 48 ms 294620 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 294224 KB Output is correct
2 Correct 42 ms 294488 KB Output is correct
3 Correct 43 ms 294484 KB Output is correct
4 Correct 43 ms 294492 KB Output is correct
5 Correct 43 ms 294484 KB Output is correct
6 Correct 44 ms 294480 KB Output is correct
7 Correct 43 ms 294252 KB Output is correct
8 Correct 42 ms 294372 KB Output is correct
9 Correct 43 ms 294492 KB Output is correct
10 Correct 43 ms 294456 KB Output is correct
11 Correct 44 ms 294484 KB Output is correct
12 Correct 43 ms 294344 KB Output is correct
13 Correct 42 ms 294352 KB Output is correct
14 Correct 43 ms 294236 KB Output is correct
15 Correct 43 ms 294236 KB Output is correct
16 Correct 47 ms 294228 KB Output is correct
17 Correct 51 ms 297476 KB Output is correct
18 Correct 52 ms 297316 KB Output is correct
19 Correct 50 ms 297300 KB Output is correct
20 Correct 46 ms 295000 KB Output is correct
21 Correct 45 ms 295248 KB Output is correct
22 Correct 46 ms 295252 KB Output is correct
23 Correct 50 ms 295248 KB Output is correct
24 Correct 48 ms 294620 KB Output is correct
25 Correct 43 ms 294236 KB Output is correct
26 Correct 43 ms 294224 KB Output is correct
27 Correct 43 ms 294484 KB Output is correct
28 Correct 42 ms 294236 KB Output is correct
29 Correct 41 ms 294224 KB Output is correct
30 Correct 242 ms 329296 KB Output is correct
31 Correct 245 ms 329556 KB Output is correct
32 Correct 240 ms 329436 KB Output is correct
33 Correct 50 ms 298320 KB Output is correct
34 Correct 63 ms 300768 KB Output is correct
35 Correct 68 ms 300960 KB Output is correct
36 Correct 60 ms 300628 KB Output is correct
37 Correct 61 ms 300372 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 294224 KB Output is correct
2 Correct 42 ms 294488 KB Output is correct
3 Correct 43 ms 294484 KB Output is correct
4 Correct 43 ms 294492 KB Output is correct
5 Correct 43 ms 294484 KB Output is correct
6 Correct 44 ms 294480 KB Output is correct
7 Correct 43 ms 294252 KB Output is correct
8 Correct 42 ms 294372 KB Output is correct
9 Correct 43 ms 294492 KB Output is correct
10 Correct 43 ms 294456 KB Output is correct
11 Correct 44 ms 294484 KB Output is correct
12 Correct 43 ms 294344 KB Output is correct
13 Correct 42 ms 294352 KB Output is correct
14 Correct 43 ms 294236 KB Output is correct
15 Correct 43 ms 294236 KB Output is correct
16 Correct 47 ms 294228 KB Output is correct
17 Correct 51 ms 297476 KB Output is correct
18 Correct 52 ms 297316 KB Output is correct
19 Correct 50 ms 297300 KB Output is correct
20 Correct 46 ms 295000 KB Output is correct
21 Correct 45 ms 295248 KB Output is correct
22 Correct 46 ms 295252 KB Output is correct
23 Correct 50 ms 295248 KB Output is correct
24 Correct 48 ms 294620 KB Output is correct
25 Correct 242 ms 329296 KB Output is correct
26 Correct 245 ms 329556 KB Output is correct
27 Correct 240 ms 329436 KB Output is correct
28 Correct 50 ms 298320 KB Output is correct
29 Correct 63 ms 300768 KB Output is correct
30 Correct 68 ms 300960 KB Output is correct
31 Correct 60 ms 300628 KB Output is correct
32 Correct 61 ms 300372 KB Output is correct
33 Correct 43 ms 294236 KB Output is correct
34 Correct 43 ms 294224 KB Output is correct
35 Correct 43 ms 294484 KB Output is correct
36 Correct 42 ms 294236 KB Output is correct
37 Correct 41 ms 294224 KB Output is correct
38 Correct 3288 ms 795036 KB Output is correct
39 Correct 2457 ms 897588 KB Output is correct
40 Correct 2556 ms 897728 KB Output is correct
41 Correct 1716 ms 999720 KB Output is correct
42 Runtime error 950 ms 1048576 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 311484 KB Output is correct
2 Correct 109 ms 311232 KB Output is correct
3 Correct 42 ms 295004 KB Output is correct
4 Correct 42 ms 294224 KB Output is correct
5 Correct 50 ms 295252 KB Output is correct
6 Correct 45 ms 295260 KB Output is correct
7 Correct 44 ms 295004 KB Output is correct
8 Correct 44 ms 294996 KB Output is correct
9 Correct 44 ms 294992 KB Output is correct
10 Correct 50 ms 294288 KB Output is correct
11 Correct 45 ms 294240 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 294236 KB Output is correct
2 Correct 43 ms 294224 KB Output is correct
3 Correct 43 ms 294484 KB Output is correct
4 Correct 42 ms 294236 KB Output is correct
5 Correct 41 ms 294224 KB Output is correct
6 Correct 43 ms 294372 KB Output is correct
7 Correct 519 ms 545364 KB Output is correct
8 Correct 1098 ms 838624 KB Output is correct
9 Correct 1109 ms 841156 KB Output is correct
10 Correct 1090 ms 841580 KB Output is correct
11 Correct 236 ms 513900 KB Output is correct
12 Correct 436 ms 711372 KB Output is correct
13 Correct 539 ms 738936 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 294224 KB Output is correct
2 Correct 42 ms 294488 KB Output is correct
3 Correct 43 ms 294484 KB Output is correct
4 Correct 43 ms 294492 KB Output is correct
5 Correct 43 ms 294484 KB Output is correct
6 Correct 44 ms 294480 KB Output is correct
7 Correct 43 ms 294252 KB Output is correct
8 Correct 42 ms 294372 KB Output is correct
9 Correct 43 ms 294492 KB Output is correct
10 Correct 43 ms 294456 KB Output is correct
11 Correct 44 ms 294484 KB Output is correct
12 Correct 43 ms 294344 KB Output is correct
13 Correct 42 ms 294352 KB Output is correct
14 Correct 43 ms 294236 KB Output is correct
15 Correct 43 ms 294236 KB Output is correct
16 Correct 47 ms 294228 KB Output is correct
17 Correct 51 ms 297476 KB Output is correct
18 Correct 52 ms 297316 KB Output is correct
19 Correct 50 ms 297300 KB Output is correct
20 Correct 46 ms 295000 KB Output is correct
21 Correct 45 ms 295248 KB Output is correct
22 Correct 46 ms 295252 KB Output is correct
23 Correct 50 ms 295248 KB Output is correct
24 Correct 48 ms 294620 KB Output is correct
25 Correct 242 ms 329296 KB Output is correct
26 Correct 245 ms 329556 KB Output is correct
27 Correct 240 ms 329436 KB Output is correct
28 Correct 50 ms 298320 KB Output is correct
29 Correct 63 ms 300768 KB Output is correct
30 Correct 68 ms 300960 KB Output is correct
31 Correct 60 ms 300628 KB Output is correct
32 Correct 61 ms 300372 KB Output is correct
33 Correct 3288 ms 795036 KB Output is correct
34 Correct 2457 ms 897588 KB Output is correct
35 Correct 2556 ms 897728 KB Output is correct
36 Correct 1716 ms 999720 KB Output is correct
37 Runtime error 950 ms 1048576 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -