oj.uz

Submission #1054815

# Submission time Handle Problem Language Result Execution time Memory
1054815 2024-08-12T12:22:14 Z mychecksedad Rectangles (IOI19_rect) C++17
50 / 100
 5000 ms 1023916 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;

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<short 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 72 ms 317780 KB Output is correct
2 Correct 75 ms 318032 KB Output is correct
3 Correct 75 ms 318036 KB Output is correct
4 Correct 73 ms 318032 KB Output is correct
5 Correct 74 ms 317736 KB Output is correct
6 Correct 74 ms 317920 KB Output is correct
7 Correct 78 ms 317780 KB Output is correct
8 Correct 73 ms 317780 KB Output is correct
9 Correct 73 ms 317776 KB Output is correct
10 Correct 83 ms 317780 KB Output is correct
11 Correct 74 ms 317776 KB Output is correct
12 Correct 74 ms 317908 KB Output is correct
13 Correct 74 ms 317780 KB Output is correct
14 Correct 71 ms 317780 KB Output is correct
15 Correct 81 ms 317848 KB Output is correct
16 Correct 82 ms 317776 KB Output is correct
17 Correct 77 ms 317776 KB Output is correct
18 Correct 72 ms 317776 KB Output is correct
19 Correct 73 ms 317876 KB Output is correct
20 Correct 72 ms 317788 KB Output is correct
21 Correct 74 ms 317776 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 317780 KB Output is correct
2 Correct 75 ms 318032 KB Output is correct
3 Correct 75 ms 318036 KB Output is correct
4 Correct 73 ms 318032 KB Output is correct
5 Correct 74 ms 317736 KB Output is correct
6 Correct 74 ms 317920 KB Output is correct
7 Correct 78 ms 317780 KB Output is correct
8 Correct 73 ms 317780 KB Output is correct
9 Correct 73 ms 317776 KB Output is correct
10 Correct 83 ms 317780 KB Output is correct
11 Correct 74 ms 317776 KB Output is correct
12 Correct 74 ms 317908 KB Output is correct
13 Correct 74 ms 317780 KB Output is correct
14 Correct 71 ms 317780 KB Output is correct
15 Correct 81 ms 317848 KB Output is correct
16 Correct 82 ms 317776 KB Output is correct
17 Correct 77 ms 317776 KB Output is correct
18 Correct 72 ms 317776 KB Output is correct
19 Correct 73 ms 317876 KB Output is correct
20 Correct 72 ms 317788 KB Output is correct
21 Correct 74 ms 317776 KB Output is correct
22 Correct 82 ms 319568 KB Output is correct
23 Correct 79 ms 319576 KB Output is correct
24 Correct 81 ms 319608 KB Output is correct
25 Correct 73 ms 318288 KB Output is correct
26 Correct 78 ms 318448 KB Output is correct
27 Correct 76 ms 318548 KB Output is correct
28 Correct 74 ms 318544 KB Output is correct
29 Correct 76 ms 318288 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 317780 KB Output is correct
2 Correct 75 ms 318032 KB Output is correct
3 Correct 75 ms 318036 KB Output is correct
4 Correct 73 ms 318032 KB Output is correct
5 Correct 74 ms 317736 KB Output is correct
6 Correct 74 ms 317920 KB Output is correct
7 Correct 78 ms 317780 KB Output is correct
8 Correct 73 ms 317780 KB Output is correct
9 Correct 73 ms 317776 KB Output is correct
10 Correct 83 ms 317780 KB Output is correct
11 Correct 74 ms 317776 KB Output is correct
12 Correct 74 ms 317908 KB Output is correct
13 Correct 74 ms 317780 KB Output is correct
14 Correct 71 ms 317780 KB Output is correct
15 Correct 81 ms 317848 KB Output is correct
16 Correct 82 ms 317776 KB Output is correct
17 Correct 82 ms 319568 KB Output is correct
18 Correct 79 ms 319576 KB Output is correct
19 Correct 81 ms 319608 KB Output is correct
20 Correct 73 ms 318288 KB Output is correct
21 Correct 78 ms 318448 KB Output is correct
22 Correct 76 ms 318548 KB Output is correct
23 Correct 74 ms 318544 KB Output is correct
24 Correct 76 ms 318288 KB Output is correct
25 Correct 77 ms 317776 KB Output is correct
26 Correct 72 ms 317776 KB Output is correct
27 Correct 73 ms 317876 KB Output is correct
28 Correct 72 ms 317788 KB Output is correct
29 Correct 74 ms 317776 KB Output is correct
30 Correct 268 ms 337748 KB Output is correct
31 Correct 277 ms 337492 KB Output is correct
32 Correct 265 ms 337776 KB Output is correct
33 Correct 82 ms 321344 KB Output is correct
34 Correct 90 ms 322900 KB Output is correct
35 Correct 95 ms 323056 KB Output is correct
36 Correct 110 ms 322812 KB Output is correct
37 Correct 92 ms 322896 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 317780 KB Output is correct
2 Correct 75 ms 318032 KB Output is correct
3 Correct 75 ms 318036 KB Output is correct
4 Correct 73 ms 318032 KB Output is correct
5 Correct 74 ms 317736 KB Output is correct
6 Correct 74 ms 317920 KB Output is correct
7 Correct 78 ms 317780 KB Output is correct
8 Correct 73 ms 317780 KB Output is correct
9 Correct 73 ms 317776 KB Output is correct
10 Correct 83 ms 317780 KB Output is correct
11 Correct 74 ms 317776 KB Output is correct
12 Correct 74 ms 317908 KB Output is correct
13 Correct 74 ms 317780 KB Output is correct
14 Correct 71 ms 317780 KB Output is correct
15 Correct 81 ms 317848 KB Output is correct
16 Correct 82 ms 317776 KB Output is correct
17 Correct 82 ms 319568 KB Output is correct
18 Correct 79 ms 319576 KB Output is correct
19 Correct 81 ms 319608 KB Output is correct
20 Correct 73 ms 318288 KB Output is correct
21 Correct 78 ms 318448 KB Output is correct
22 Correct 76 ms 318548 KB Output is correct
23 Correct 74 ms 318544 KB Output is correct
24 Correct 76 ms 318288 KB Output is correct
25 Correct 268 ms 337748 KB Output is correct
26 Correct 277 ms 337492 KB Output is correct
27 Correct 265 ms 337776 KB Output is correct
28 Correct 82 ms 321344 KB Output is correct
29 Correct 90 ms 322900 KB Output is correct
30 Correct 95 ms 323056 KB Output is correct
31 Correct 110 ms 322812 KB Output is correct
32 Correct 92 ms 322896 KB Output is correct
33 Correct 77 ms 317776 KB Output is correct
34 Correct 72 ms 317776 KB Output is correct
35 Correct 73 ms 317876 KB Output is correct
36 Correct 72 ms 317788 KB Output is correct
37 Correct 74 ms 317776 KB Output is correct
38 Correct 3177 ms 592620 KB Output is correct
39 Correct 2387 ms 645788 KB Output is correct
40 Correct 2515 ms 645704 KB Output is correct
41 Correct 1766 ms 698024 KB Output is correct
42 Execution timed out 5112 ms 1023916 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 326756 KB Output is correct
2 Correct 127 ms 326532 KB Output is correct
3 Correct 60 ms 318292 KB Output is correct
4 Correct 60 ms 317780 KB Output is correct
5 Correct 64 ms 318456 KB Output is correct
6 Correct 62 ms 318548 KB Output is correct
7 Correct 61 ms 318800 KB Output is correct
8 Correct 61 ms 318604 KB Output is correct
9 Correct 62 ms 318612 KB Output is correct
10 Correct 61 ms 317780 KB Output is correct
11 Correct 59 ms 317780 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 317776 KB Output is correct
2 Correct 72 ms 317776 KB Output is correct
3 Correct 73 ms 317876 KB Output is correct
4 Correct 72 ms 317788 KB Output is correct
5 Correct 74 ms 317776 KB Output is correct
6 Correct 60 ms 317908 KB Output is correct
7 Correct 527 ms 547156 KB Output is correct
8 Correct 1125 ms 815508 KB Output is correct
9 Correct 1150 ms 816896 KB Output is correct
10 Correct 1117 ms 817164 KB Output is correct
11 Correct 264 ms 515412 KB Output is correct
12 Correct 454 ms 693268 KB Output is correct
13 Correct 507 ms 717904 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 317780 KB Output is correct
2 Correct 75 ms 318032 KB Output is correct
3 Correct 75 ms 318036 KB Output is correct
4 Correct 73 ms 318032 KB Output is correct
5 Correct 74 ms 317736 KB Output is correct
6 Correct 74 ms 317920 KB Output is correct
7 Correct 78 ms 317780 KB Output is correct
8 Correct 73 ms 317780 KB Output is correct
9 Correct 73 ms 317776 KB Output is correct
10 Correct 83 ms 317780 KB Output is correct
11 Correct 74 ms 317776 KB Output is correct
12 Correct 74 ms 317908 KB Output is correct
13 Correct 74 ms 317780 KB Output is correct
14 Correct 71 ms 317780 KB Output is correct
15 Correct 81 ms 317848 KB Output is correct
16 Correct 82 ms 317776 KB Output is correct
17 Correct 82 ms 319568 KB Output is correct
18 Correct 79 ms 319576 KB Output is correct
19 Correct 81 ms 319608 KB Output is correct
20 Correct 73 ms 318288 KB Output is correct
21 Correct 78 ms 318448 KB Output is correct
22 Correct 76 ms 318548 KB Output is correct
23 Correct 74 ms 318544 KB Output is correct
24 Correct 76 ms 318288 KB Output is correct
25 Correct 268 ms 337748 KB Output is correct
26 Correct 277 ms 337492 KB Output is correct
27 Correct 265 ms 337776 KB Output is correct
28 Correct 82 ms 321344 KB Output is correct
29 Correct 90 ms 322900 KB Output is correct
30 Correct 95 ms 323056 KB Output is correct
31 Correct 110 ms 322812 KB Output is correct
32 Correct 92 ms 322896 KB Output is correct
33 Correct 3177 ms 592620 KB Output is correct
34 Correct 2387 ms 645788 KB Output is correct
35 Correct 2515 ms 645704 KB Output is correct
36 Correct 1766 ms 698024 KB Output is correct
37 Execution timed out 5112 ms 1023916 KB Time limit exceeded
38 Halted 0 ms 0 KB -