oj.uz

Submission #242765

# Submission time Handle Problem Language Result Execution time Memory
242765 2020-06-29T09:13:46 Z Lawliet Rectangles (IOI19_rect) C++17
100 / 100
 3555 ms 884084 KB 
#include <bits/stdc++.h>
#include "rect.h"
 
using namespace std;
typedef pair<int,int> pii;
 
const int LOG = 12;
const int MAXN = 2510;
const int INF = 1000000010;
const int MAXS = 2500*2500 + 10;

struct query
{
	int L, R;
	int ind, k;

	query(int l, int r, int i, int k)
		: L(l), R(r), ind(i), k(k) {}
};

class RMQ
{
	public:

		int cmp(int a, int b, int t)
		{
			if( t == 0 ) return max( a , b );
			return min( a,  b );
		}

		void build(vector<int>& v, int t)
		{
			int n = (int)v.size();

			for(int i = 1 ; i <= n ; i++)
				tab[0][i] = v[i - 1];

			for(int k = 0 ; k < LOG - 1 ; k++)
				for(int L = 1 ; L + (1 << (k + 1)) <= n + 1 ; L++)
					tab[k + 1][L] = cmp( tab[k][L] , tab[k][L + (1 << k)] , t );
		}

		int query(int L, int R, int t)
		{
			int sz = R - L + 1;
			int k = 31 - __builtin_clz(sz);

			return cmp( tab[k][L] , tab[k][R + 1 - (1 << k)] , t );
		}

	private:

		int tab[LOG][MAXN];
};
 
int n, m;
 
int v[MAXN][MAXN], qtd[MAXS];
int L[MAXN][MAXN], U[MAXN][MAXN];
int R[MAXN][MAXN][2], D[MAXN][MAXN][2];

vector<query> lineMin[MAXN], columnMin[MAXN];
vector<query> lineMax[MAXN], columnMax[MAXN];

RMQ curRMQ;
 
void makeHistogram()
{
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= m ; j++)
		{
			int& ansL = L[i][j]; ansL = j - 1;
			int& ansU = U[i][j]; ansU = i - 1;

			while( v[i][ansL] < v[i][j] ) ansL = L[i][ansL];
			while( v[ansU][j] < v[i][j] ) ansU = U[ansU][j];
		}
	}

	for(int j = m ; j > 0 ; j--)
	{
		for(int i = n ; i > 0 ; i--)
		{
			int ansR[2] = { j + 1 , j + 1 };
			int ansD[2] = { i + 1 , i + 1 };
 
 			while( v[i][ ansR[1] ] < v[i][j] ) ansR[1] = R[i][ ansR[1] ][1];
			while( v[i][ ansR[0] ] <= v[i][j] ) ansR[0] = R[i][ ansR[0] ][0];

			while( v[ ansD[1] ][j] < v[i][j] ) ansD[1] = D[ ansD[1] ][j][1];
			while( v[ ansD[0] ][j] <= v[i][j] ) ansD[0] = D[ ansD[0] ][j][0];

			R[i][j][0] = ansR[0]; R[i][j][1] = ansR[1];
			D[i][j][0] = ansD[0]; D[i][j][1] = ansD[1]; 
		}
	}
}
 
long long count_rectangles(vector< vector<int> > a)
{
	n = a.size();
	m = a[0].size();

	for(int i = 0 ; i <= n + 1 ; i++)
		for(int j = 0 ; j <= m + 1 ; j++)
			v[i][j] = INF;
 
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < m ; j++)
			v[i + 1][j + 1] = a[i][j];
 
	makeHistogram();
 
	vector< pair<pii,pii> > rect;
 
	for(int i = 2 ; i < n ; i++)
	{
		for(int j = 2 ; j < m ; j++)
		{
			if( L[i][j] == 0 || U[i][j] == 0 ) continue;
			if( R[i][j][0] == m + 1 || D[i][j][0] == n + 1 ) continue;
 
			pii dY = { L[i][j] + 1 , R[i][j][0] - 1 };
			pii dX = { U[i][j] + 1 , D[i][j][0] - 1 };
 
			rect.push_back( { dX , dY } );
		}
	}

	sort( rect.begin() , rect.end() );

	auto it = unique( rect.begin() , rect.end() );
	rect.resize( it - rect.begin() );
  
	for(int i = 0 ; i < (int)rect.size() ; i++)
	{
		int x1 = rect[i].first.first;
		int x2 = rect[i].first.second;
		int y1 = rect[i].second.first;
		int y2 = rect[i].second.second;

		lineMin[x1 - 1].push_back( query( y1 , y2 , i , x2 ) );
		lineMax[x2 + 1].push_back( query( y1 , y2 , i , x1 ) );

		columnMin[y1 - 1].push_back( query( x1 , x2 , i , y2 ) );
		columnMax[y2 + 1].push_back( query( x1 , x2 , i , y1 ) );
	}

	for(int i = 1 ; i <= n ; i++)
	{
		vector<int> curMx, curMn;

		for(int j = 1 ; j <= m ; j++)
		{
			curMx.push_back( U[i][j] );
			curMn.push_back( D[i][j][1] );
		}

		curRMQ.build( curMx , 0 );

		while( !lineMax[i].empty() )
		{
			int k = lineMax[i].back().k;
			int curL = lineMax[i].back().L;
			int curR = lineMax[i].back().R;
			int ind = lineMax[i].back().ind;
			lineMax[i].pop_back();

			if( curRMQ.query( curL , curR , 0 ) >= k )
				qtd[ind]++;
		}

		curRMQ.build( curMn , 1 );

		while( !lineMin[i].empty() )
		{
			int k = lineMin[i].back().k;
			int curL = lineMin[i].back().L;
			int curR = lineMin[i].back().R;
			int ind = lineMin[i].back().ind;
			lineMin[i].pop_back();

			if( curRMQ.query( curL , curR , 1 ) <= k )
				qtd[ind]++;
		}
	}

	for(int j = 1 ; j <= m ; j++)
	{
		vector<int> curMx, curMn;

		for(int i = 1 ; i <= n ; i++)
		{
			curMx.push_back( L[i][j] );
			curMn.push_back( R[i][j][1] );
		}

		curRMQ.build( curMx , 0 );

		while( !columnMax[j].empty() )
		{
			int k = columnMax[j].back().k;
			int curL = columnMax[j].back().L;
			int curR = columnMax[j].back().R;
			int ind = columnMax[j].back().ind;
			columnMax[j].pop_back();

			if( curRMQ.query( curL , curR , 0 ) >= k )
				qtd[ind]++;
		}

		curRMQ.build( curMn , 1 );

		while( !columnMin[j].empty() )
		{
			int k = columnMin[j].back().k;
			int curL = columnMin[j].back().L;
			int curR = columnMin[j].back().R;
			int ind = columnMin[j].back().ind;
			columnMin[j].pop_back();

			if( curRMQ.query( curL , curR , 1 ) <= k )
				qtd[ind]++;
		}
	}

	int ans = 0;

	for(int i = 0 ; i < (int)rect.size() ; i++)
		if( qtd[i] == 0 ) ans++;
 
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 896 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 5 ms 640 KB Output is correct
19 Correct 5 ms 1280 KB Output is correct
20 Correct 5 ms 1280 KB Output is correct
21 Correct 5 ms 768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 896 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 8 ms 3072 KB Output is correct
18 Correct 7 ms 3072 KB Output is correct
19 Correct 7 ms 3072 KB Output is correct
20 Correct 8 ms 2944 KB Output is correct
21 Correct 8 ms 3072 KB Output is correct
22 Correct 8 ms 3200 KB Output is correct
23 Correct 9 ms 3072 KB Output is correct
24 Correct 7 ms 2560 KB Output is correct
25 Correct 5 ms 640 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 5 ms 1280 KB Output is correct
29 Correct 5 ms 768 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 896 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 8 ms 3072 KB Output is correct
18 Correct 7 ms 3072 KB Output is correct
19 Correct 7 ms 3072 KB Output is correct
20 Correct 8 ms 2944 KB Output is correct
21 Correct 8 ms 3072 KB Output is correct
22 Correct 8 ms 3200 KB Output is correct
23 Correct 9 ms 3072 KB Output is correct
24 Correct 7 ms 2560 KB Output is correct
25 Correct 18 ms 10616 KB Output is correct
26 Correct 19 ms 10616 KB Output is correct
27 Correct 19 ms 10744 KB Output is correct
28 Correct 19 ms 9340 KB Output is correct
29 Correct 23 ms 10360 KB Output is correct
30 Correct 25 ms 10480 KB Output is correct
31 Correct 24 ms 10488 KB Output is correct
32 Correct 23 ms 10484 KB Output is correct
33 Correct 5 ms 640 KB Output is correct
34 Correct 5 ms 640 KB Output is correct
35 Correct 5 ms 1280 KB Output is correct
36 Correct 5 ms 1280 KB Output is correct
37 Correct 5 ms 768 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 896 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 8 ms 3072 KB Output is correct
18 Correct 7 ms 3072 KB Output is correct
19 Correct 7 ms 3072 KB Output is correct
20 Correct 8 ms 2944 KB Output is correct
21 Correct 8 ms 3072 KB Output is correct
22 Correct 8 ms 3200 KB Output is correct
23 Correct 9 ms 3072 KB Output is correct
24 Correct 7 ms 2560 KB Output is correct
25 Correct 18 ms 10616 KB Output is correct
26 Correct 19 ms 10616 KB Output is correct
27 Correct 19 ms 10744 KB Output is correct
28 Correct 19 ms 9340 KB Output is correct
29 Correct 23 ms 10360 KB Output is correct
30 Correct 25 ms 10480 KB Output is correct
31 Correct 24 ms 10488 KB Output is correct
32 Correct 23 ms 10484 KB Output is correct
33 Correct 94 ms 35320 KB Output is correct
34 Correct 93 ms 35324 KB Output is correct
35 Correct 98 ms 35448 KB Output is correct
36 Correct 106 ms 35320 KB Output is correct
37 Correct 187 ms 80208 KB Output is correct
38 Correct 185 ms 80208 KB Output is correct
39 Correct 184 ms 80596 KB Output is correct
40 Correct 176 ms 76304 KB Output is correct
41 Correct 164 ms 62104 KB Output is correct
42 Correct 179 ms 63828 KB Output is correct
43 Correct 239 ms 88272 KB Output is correct
44 Correct 256 ms 90040 KB Output is correct
45 Correct 126 ms 51936 KB Output is correct
46 Correct 119 ms 45664 KB Output is correct
47 Correct 242 ms 87120 KB Output is correct
48 Correct 244 ms 87764 KB Output is correct
49 Correct 5 ms 640 KB Output is correct
50 Correct 5 ms 640 KB Output is correct
51 Correct 5 ms 1280 KB Output is correct
52 Correct 5 ms 1280 KB Output is correct
53 Correct 5 ms 768 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1280 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 6 ms 1024 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct
7 Correct 7 ms 1152 KB Output is correct
8 Correct 7 ms 1152 KB Output is correct
9 Correct 7 ms 1152 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 6 ms 1024 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 887 ms 274516 KB Output is correct
3 Correct 1917 ms 569276 KB Output is correct
4 Correct 1899 ms 571860 KB Output is correct
5 Correct 1928 ms 571860 KB Output is correct
6 Correct 555 ms 115960 KB Output is correct
7 Correct 1100 ms 230136 KB Output is correct
8 Correct 1207 ms 234128 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 5 ms 768 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 896 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 8 ms 3072 KB Output is correct
18 Correct 7 ms 3072 KB Output is correct
19 Correct 7 ms 3072 KB Output is correct
20 Correct 8 ms 2944 KB Output is correct
21 Correct 8 ms 3072 KB Output is correct
22 Correct 8 ms 3200 KB Output is correct
23 Correct 9 ms 3072 KB Output is correct
24 Correct 7 ms 2560 KB Output is correct
25 Correct 18 ms 10616 KB Output is correct
26 Correct 19 ms 10616 KB Output is correct
27 Correct 19 ms 10744 KB Output is correct
28 Correct 19 ms 9340 KB Output is correct
29 Correct 23 ms 10360 KB Output is correct
30 Correct 25 ms 10480 KB Output is correct
31 Correct 24 ms 10488 KB Output is correct
32 Correct 23 ms 10484 KB Output is correct
33 Correct 94 ms 35320 KB Output is correct
34 Correct 93 ms 35324 KB Output is correct
35 Correct 98 ms 35448 KB Output is correct
36 Correct 106 ms 35320 KB Output is correct
37 Correct 187 ms 80208 KB Output is correct
38 Correct 185 ms 80208 KB Output is correct
39 Correct 184 ms 80596 KB Output is correct
40 Correct 176 ms 76304 KB Output is correct
41 Correct 164 ms 62104 KB Output is correct
42 Correct 179 ms 63828 KB Output is correct
43 Correct 239 ms 88272 KB Output is correct
44 Correct 256 ms 90040 KB Output is correct
45 Correct 126 ms 51936 KB Output is correct
46 Correct 119 ms 45664 KB Output is correct
47 Correct 242 ms 87120 KB Output is correct
48 Correct 244 ms 87764 KB Output is correct
49 Correct 8 ms 1280 KB Output is correct
50 Correct 7 ms 1408 KB Output is correct
51 Correct 6 ms 1024 KB Output is correct
52 Correct 5 ms 640 KB Output is correct
53 Correct 7 ms 1152 KB Output is correct
54 Correct 7 ms 1280 KB Output is correct
55 Correct 7 ms 1152 KB Output is correct
56 Correct 7 ms 1152 KB Output is correct
57 Correct 7 ms 1152 KB Output is correct
58 Correct 5 ms 896 KB Output is correct
59 Correct 6 ms 1024 KB Output is correct
60 Correct 5 ms 896 KB Output is correct
61 Correct 887 ms 274516 KB Output is correct
62 Correct 1917 ms 569276 KB Output is correct
63 Correct 1899 ms 571860 KB Output is correct
64 Correct 1928 ms 571860 KB Output is correct
65 Correct 555 ms 115960 KB Output is correct
66 Correct 1100 ms 230136 KB Output is correct
67 Correct 1207 ms 234128 KB Output is correct
68 Correct 1249 ms 247736 KB Output is correct
69 Correct 1255 ms 248952 KB Output is correct
70 Correct 1352 ms 247564 KB Output is correct
71 Correct 1340 ms 247544 KB Output is correct
72 Correct 2715 ms 791684 KB Output is correct
73 Correct 1903 ms 514900 KB Output is correct
74 Correct 2135 ms 601960 KB Output is correct
75 Correct 3358 ms 880180 KB Output is correct
76 Correct 2033 ms 529624 KB Output is correct
77 Correct 2759 ms 711932 KB Output is correct
78 Correct 3555 ms 884084 KB Output is correct
79 Correct 1884 ms 524416 KB Output is correct
80 Correct 3269 ms 872056 KB Output is correct
81 Correct 3208 ms 845464 KB Output is correct
82 Correct 1477 ms 539468 KB Output is correct
83 Correct 2614 ms 791244 KB Output is correct
84 Correct 2573 ms 791612 KB Output is correct
85 Correct 2629 ms 791588 KB Output is correct
86 Correct 5 ms 640 KB Output is correct
87 Correct 5 ms 640 KB Output is correct
88 Correct 5 ms 1280 KB Output is correct
89 Correct 5 ms 1280 KB Output is correct
90 Correct 5 ms 768 KB Output is correct