oj.uz

Submission #1054867

# Submission time Handle Problem Language Result Execution time Memory
1054867 2024-08-12T12:47:38 Z mychecksedad Rectangles (IOI19_rect) C++17
50 / 100
 3176 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];
				}	
			}
		}
	}
	L.clear();
	R.clear();
	D.clear();
	U.clear();
// 	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:212:59: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  212 |     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 41 ms 294232 KB Output is correct
2 Correct 40 ms 294492 KB Output is correct
3 Correct 39 ms 294480 KB Output is correct
4 Correct 41 ms 294480 KB Output is correct
5 Correct 41 ms 294484 KB Output is correct
6 Correct 42 ms 294480 KB Output is correct
7 Correct 40 ms 294492 KB Output is correct
8 Correct 40 ms 294224 KB Output is correct
9 Correct 40 ms 294492 KB Output is correct
10 Correct 40 ms 294480 KB Output is correct
11 Correct 42 ms 294484 KB Output is correct
12 Correct 41 ms 294356 KB Output is correct
13 Correct 40 ms 294224 KB Output is correct
14 Correct 44 ms 294236 KB Output is correct
15 Correct 41 ms 294236 KB Output is correct
16 Correct 40 ms 294228 KB Output is correct
17 Correct 41 ms 294236 KB Output is correct
18 Correct 42 ms 294236 KB Output is correct
19 Correct 40 ms 294484 KB Output is correct
20 Correct 40 ms 294228 KB Output is correct
21 Correct 40 ms 294232 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 294232 KB Output is correct
2 Correct 40 ms 294492 KB Output is correct
3 Correct 39 ms 294480 KB Output is correct
4 Correct 41 ms 294480 KB Output is correct
5 Correct 41 ms 294484 KB Output is correct
6 Correct 42 ms 294480 KB Output is correct
7 Correct 40 ms 294492 KB Output is correct
8 Correct 40 ms 294224 KB Output is correct
9 Correct 40 ms 294492 KB Output is correct
10 Correct 40 ms 294480 KB Output is correct
11 Correct 42 ms 294484 KB Output is correct
12 Correct 41 ms 294356 KB Output is correct
13 Correct 40 ms 294224 KB Output is correct
14 Correct 44 ms 294236 KB Output is correct
15 Correct 41 ms 294236 KB Output is correct
16 Correct 40 ms 294228 KB Output is correct
17 Correct 41 ms 294236 KB Output is correct
18 Correct 42 ms 294236 KB Output is correct
19 Correct 40 ms 294484 KB Output is correct
20 Correct 40 ms 294228 KB Output is correct
21 Correct 40 ms 294232 KB Output is correct
22 Correct 48 ms 297308 KB Output is correct
23 Correct 47 ms 297308 KB Output is correct
24 Correct 47 ms 297308 KB Output is correct
25 Correct 42 ms 294992 KB Output is correct
26 Correct 42 ms 295172 KB Output is correct
27 Correct 43 ms 295248 KB Output is correct
28 Correct 42 ms 295260 KB Output is correct
29 Correct 40 ms 294736 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 294232 KB Output is correct
2 Correct 40 ms 294492 KB Output is correct
3 Correct 39 ms 294480 KB Output is correct
4 Correct 41 ms 294480 KB Output is correct
5 Correct 41 ms 294484 KB Output is correct
6 Correct 42 ms 294480 KB Output is correct
7 Correct 40 ms 294492 KB Output is correct
8 Correct 40 ms 294224 KB Output is correct
9 Correct 40 ms 294492 KB Output is correct
10 Correct 40 ms 294480 KB Output is correct
11 Correct 42 ms 294484 KB Output is correct
12 Correct 41 ms 294356 KB Output is correct
13 Correct 40 ms 294224 KB Output is correct
14 Correct 44 ms 294236 KB Output is correct
15 Correct 41 ms 294236 KB Output is correct
16 Correct 40 ms 294228 KB Output is correct
17 Correct 48 ms 297308 KB Output is correct
18 Correct 47 ms 297308 KB Output is correct
19 Correct 47 ms 297308 KB Output is correct
20 Correct 42 ms 294992 KB Output is correct
21 Correct 42 ms 295172 KB Output is correct
22 Correct 43 ms 295248 KB Output is correct
23 Correct 42 ms 295260 KB Output is correct
24 Correct 40 ms 294736 KB Output is correct
25 Correct 41 ms 294236 KB Output is correct
26 Correct 42 ms 294236 KB Output is correct
27 Correct 40 ms 294484 KB Output is correct
28 Correct 40 ms 294228 KB Output is correct
29 Correct 40 ms 294232 KB Output is correct
30 Correct 239 ms 329140 KB Output is correct
31 Correct 244 ms 329040 KB Output is correct
32 Correct 241 ms 329020 KB Output is correct
33 Correct 46 ms 298064 KB Output is correct
34 Correct 59 ms 300372 KB Output is correct
35 Correct 60 ms 300372 KB Output is correct
36 Correct 57 ms 300372 KB Output is correct
37 Correct 58 ms 300260 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 294232 KB Output is correct
2 Correct 40 ms 294492 KB Output is correct
3 Correct 39 ms 294480 KB Output is correct
4 Correct 41 ms 294480 KB Output is correct
5 Correct 41 ms 294484 KB Output is correct
6 Correct 42 ms 294480 KB Output is correct
7 Correct 40 ms 294492 KB Output is correct
8 Correct 40 ms 294224 KB Output is correct
9 Correct 40 ms 294492 KB Output is correct
10 Correct 40 ms 294480 KB Output is correct
11 Correct 42 ms 294484 KB Output is correct
12 Correct 41 ms 294356 KB Output is correct
13 Correct 40 ms 294224 KB Output is correct
14 Correct 44 ms 294236 KB Output is correct
15 Correct 41 ms 294236 KB Output is correct
16 Correct 40 ms 294228 KB Output is correct
17 Correct 48 ms 297308 KB Output is correct
18 Correct 47 ms 297308 KB Output is correct
19 Correct 47 ms 297308 KB Output is correct
20 Correct 42 ms 294992 KB Output is correct
21 Correct 42 ms 295172 KB Output is correct
22 Correct 43 ms 295248 KB Output is correct
23 Correct 42 ms 295260 KB Output is correct
24 Correct 40 ms 294736 KB Output is correct
25 Correct 239 ms 329140 KB Output is correct
26 Correct 244 ms 329040 KB Output is correct
27 Correct 241 ms 329020 KB Output is correct
28 Correct 46 ms 298064 KB Output is correct
29 Correct 59 ms 300372 KB Output is correct
30 Correct 60 ms 300372 KB Output is correct
31 Correct 57 ms 300372 KB Output is correct
32 Correct 58 ms 300260 KB Output is correct
33 Correct 41 ms 294236 KB Output is correct
34 Correct 42 ms 294236 KB Output is correct
35 Correct 40 ms 294484 KB Output is correct
36 Correct 40 ms 294228 KB Output is correct
37 Correct 40 ms 294232 KB Output is correct
38 Correct 3176 ms 786244 KB Output is correct
39 Correct 2454 ms 888956 KB Output is correct
40 Correct 2503 ms 888936 KB Output is correct
41 Correct 1729 ms 990904 KB Output is correct
42 Runtime error 1035 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 153 ms 311740 KB Output is correct
2 Correct 118 ms 311596 KB Output is correct
3 Correct 47 ms 294928 KB Output is correct
4 Correct 50 ms 294228 KB Output is correct
5 Correct 42 ms 295104 KB Output is correct
6 Correct 43 ms 295004 KB Output is correct
7 Correct 43 ms 295028 KB Output is correct
8 Correct 41 ms 295032 KB Output is correct
9 Correct 42 ms 295140 KB Output is correct
10 Correct 52 ms 294228 KB Output is correct
11 Correct 52 ms 294228 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 294236 KB Output is correct
2 Correct 42 ms 294236 KB Output is correct
3 Correct 40 ms 294484 KB Output is correct
4 Correct 40 ms 294228 KB Output is correct
5 Correct 40 ms 294232 KB Output is correct
6 Correct 40 ms 294228 KB Output is correct
7 Correct 502 ms 542744 KB Output is correct
8 Correct 1292 ms 833588 KB Output is correct
9 Correct 1118 ms 836244 KB Output is correct
10 Correct 1091 ms 836440 KB Output is correct
11 Correct 243 ms 512092 KB Output is correct
12 Correct 423 ms 708004 KB Output is correct
13 Correct 445 ms 735420 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 294232 KB Output is correct
2 Correct 40 ms 294492 KB Output is correct
3 Correct 39 ms 294480 KB Output is correct
4 Correct 41 ms 294480 KB Output is correct
5 Correct 41 ms 294484 KB Output is correct
6 Correct 42 ms 294480 KB Output is correct
7 Correct 40 ms 294492 KB Output is correct
8 Correct 40 ms 294224 KB Output is correct
9 Correct 40 ms 294492 KB Output is correct
10 Correct 40 ms 294480 KB Output is correct
11 Correct 42 ms 294484 KB Output is correct
12 Correct 41 ms 294356 KB Output is correct
13 Correct 40 ms 294224 KB Output is correct
14 Correct 44 ms 294236 KB Output is correct
15 Correct 41 ms 294236 KB Output is correct
16 Correct 40 ms 294228 KB Output is correct
17 Correct 48 ms 297308 KB Output is correct
18 Correct 47 ms 297308 KB Output is correct
19 Correct 47 ms 297308 KB Output is correct
20 Correct 42 ms 294992 KB Output is correct
21 Correct 42 ms 295172 KB Output is correct
22 Correct 43 ms 295248 KB Output is correct
23 Correct 42 ms 295260 KB Output is correct
24 Correct 40 ms 294736 KB Output is correct
25 Correct 239 ms 329140 KB Output is correct
26 Correct 244 ms 329040 KB Output is correct
27 Correct 241 ms 329020 KB Output is correct
28 Correct 46 ms 298064 KB Output is correct
29 Correct 59 ms 300372 KB Output is correct
30 Correct 60 ms 300372 KB Output is correct
31 Correct 57 ms 300372 KB Output is correct
32 Correct 58 ms 300260 KB Output is correct
33 Correct 3176 ms 786244 KB Output is correct
34 Correct 2454 ms 888956 KB Output is correct
35 Correct 2503 ms 888936 KB Output is correct
36 Correct 1729 ms 990904 KB Output is correct
37 Runtime error 1035 ms 1048576 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -