oj.uz

Submission #1008795

# Submission time Handle Problem Language Result Execution time Memory
1008795 2024-06-26T18:37:50 Z PagodePaiva Rectangles (IOI19_rect) C++17
18 / 100
 1152 ms 486664 KB 
#include "rect.h"
#include <bits/stdc++.h>
#define int int16_t

using namespace std;

const int N = 2510;
const int inf = N;
const int LOGN = 12;

int32_t v[N][N];
int p1[N][N];
int p2[N][N];
int p3[N][N];
int p4[N][N];
int lg2[N];

int logg2(int x){
	return lg2[x];
}

struct RMQmin{
	int val[N][LOGN];
	int n;
	void build(vector <int> v){
		for(int i = 0;i < N;i++){
			for(int j = 0;j < LOGN;j++){
				val[i][j] = inf;
			}
		}
		n = v.size();
		for(int i = 1;i <= n;i++){
			val[i][0] = v[i-1];
		}
		for(int j = 1;j < LOGN;j++){
			for(int i = 1;i <= n;i++){
				if((i+(1<< (j-1))) > n) val[i][j] = val[i][j-1];
				else val[i][j] = min(val[i][j-1], val[(i+(1 << (j-1)))][j-1]);
			}
		}
		return;
	}
	int query(int l, int r){
		int t = logg2(r-l+1);
		return min(val[l][t], val[(r-(1<<t)+1)][t]);
	}
} seg1[N], seg3[N];

struct RMQmax{
	int val[N][LOGN];
	int n;
	void build(vector <int> v){
		for(int i = 0;i < N;i++){
			for(int j = 0;j < LOGN;j++){
				val[i][j] = 0;
			}
		}
		n = v.size();
		for(int i = 1;i <= n;i++){
			val[i][0] = v[i-1];
		}
		for(int j = 1;j < LOGN;j++){
			for(int i = 1;i <= n;i++){
				if((i+(1<< (j-1))) > n) val[i][j] = val[i][j-1];
				else val[i][j] = max(val[i][j-1], val[(i+(1 << (j-1)))][j-1]);
			}
		}
		return;
	}
	int query(int l, int r){
		int t = logg2(r-l+1);
		return max(val[l][t], val[(r-(1<<t)+1)][t]);
	}
} seg2[N], seg4[N];

set <int> s;
int n, m;

bool check(int r1, int c1, int r2, int c2){
	if(r1 == 0 or r2 == n+1 or r2-r1 <= 1) return false;
	if(c1 == 0 or c2 == m+1 or c2-c1 <= 1) return false;
	if(r1+1 > r2-1 or c1+1 > c2-1) return false;
	if(c1 <= 0 or c1 > m or c2 <= 0 or c2 > m or r1 <= 0 or r1 > n or r2 <= 0 or r2 > n) return false;
	int x1 = seg1[c1].query(r1+1, r2-1);
	if(c1+1 <= x1 and x1 <= c2-1) return false;
	x1 = seg2[c2].query(r1+1, r2-1);
	if(c1 < x1 and x1 < c2) return false;
	int x2 = seg3[r1].query(c1+1, c2-1);
	if(r1 < x2 and x2 < r2) return false;
	x2 = seg4[r2].query(c1+1, c2-1);
	if(r1 < x2 and x2 < r2) return false;
	if(s.find(r1+c1*N+r2*N*N+c2*N*N*N) != s.end()) return false;
	s.insert(r1+c1*N+r2*N*N+c2*N*N*N);
	return true;
}
long long count_rectangles(std::vector<std::vector<int32_t> > a) {
	lg2[0] = 0;
	lg2[1] = 0;
	for(int i = 2;i < N;i++){
		int t = i/2;
		lg2[i] = lg2[t]+1;
	}
	n = a.size(), m = a[0].size();
	s.clear();
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			v[i][j] = a[i-1][j-1];
		}
	}
	for(int i = 1;i <= n;i++){
		stack <int> s;
		for(int j = 1;j <= m;j++){
			if(s.empty()) s.push(j);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[i][t]){
						p1[i][t] = j;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(j);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p1[i][t] = m+1;
			s.pop();
		}
	}
	for(int i = 1;i <= n;i++){
		stack <int> s;
		for(int j = m;j > 0;j--){
			if(s.empty()) s.push(j);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[i][t]){
						p2[i][t] = j;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(j);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p2[i][t] = 0;
			s.pop();
		}
	}
	for(int j = 1;j <= m;j++){
		stack <int> s;
		for(int i = 1;i <= n;i++){
			if(s.empty()) s.push(i);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[t][j]){
						p3[t][j] = i;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(i);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p3[t][j] = n+1;
			s.pop();
		}
	}
	for(int j = 1;j <= m;j++){
		stack <int> s;
		for(int i = n;i > 0;i--){
			if(s.empty()) s.push(i);
			else{
				while(!s.empty()){
					int t = s.top();
					if(v[i][j] >= v[t][j]){
						p4[t][j] = i;
						s.pop();
					}
					else{
						break;
					}
				}
				s.push(i);
			}
		}
		while(!s.empty()){
			int t = s.top();
			p4[t][j] = 0;
			s.pop();
		}
	}
	for(int i = 1;i <= n;i++){
		vector <int> aux1, aux2;
		for(int j = 1;j <= m;j++){
			aux1.push_back(p3[i][j]);
			aux2.push_back(p4[i][j]);
		}
		seg3[i].build(aux1);
		seg4[i].build(aux2);
	}
	for(int j = 1;j <= m;j++){
		vector <int> aux1, aux2;
		for(int i = 1;i <= n;i++){
			aux1.push_back(p1[i][j]);
			aux2.push_back(p2[i][j]);
		}
		seg1[j].build(aux1);
		seg2[j].build(aux2);
	}
	for(int r1 = 1;r1 < n;r1++){
		for(int c1 = 1;c1 < m;c1++){
			int r2 = p3[r1][c1+1];
			int c2 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg1[c1].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
			c2 = p1[r1+1][c1];
			r2 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg3[r1].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
		}
	}
	for(int r1 = 1;r1 < n;r1++){
		for(int c2 = m;c2 > 1;c2--){
			int c1 = p2[r1+1][c2];
			int r2 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg3[r1].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
			r2 = p3[r1][c2-1];
			c1 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg2[c2].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
		}
	}
	for(int r2 = n;r2 > 1;r2--){
		for(int c1 = 1;c1 < m;c1++){
			int r1 = p4[r2][c1+1];
			int c2 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg1[c1].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
			c2 = p1[r2-1][c1];
			r1 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg4[r2].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
			/*
			int c2 = p1[r2-1][c1];
			int r1 = p4[r2][c1+1];
			check(r1, c1, r2, c2);
			*/
		}
	}
	for(int r2 = n;r2 > 1;r2--){
		for(int c2 = m;c2 > 1;c2--){
			int c1 = p2[r2-1][c2];
			int r1 = (1 <= c1+1 and c1+1 <= c2-1 and c2-1 <= m ? seg4[r2].query(c1+1, c2-1) : -1);
			check(r1, c1, r2, c2);
			r1 = p4[r2][c2-1];
			c1 = (1 <= r1+1 and r1+1 <= r2-1 and r2-1 <= n ? seg2[c2].query(r1+1, r2-1) : -1);
			check(r1, c1, r2, c2);
			/*
			int c1 = p2[r2-1][c2];
			int r1 = p4[r2][c2-1];
			check(r1, c1, r2, c2);
			*/
		}
	}
	long long res = s.size();
	return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 4 ms 7988 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 6 ms 8120 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 5 ms 8116 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 7976 KB Output is correct
12 Correct 5 ms 8052 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 1208 KB Output is correct
19 Correct 4 ms 8044 KB Output is correct
20 Correct 3 ms 6492 KB Output is correct
21 Correct 1 ms 1880 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 4 ms 7988 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 6 ms 8120 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 5 ms 8116 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 7976 KB Output is correct
12 Correct 5 ms 8052 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 1208 KB Output is correct
19 Correct 4 ms 8044 KB Output is correct
20 Correct 3 ms 6492 KB Output is correct
21 Correct 1 ms 1880 KB Output is correct
22 Correct 11 ms 21336 KB Output is correct
23 Correct 11 ms 21340 KB Output is correct
24 Correct 12 ms 21340 KB Output is correct
25 Correct 11 ms 21084 KB Output is correct
26 Incorrect 16 ms 20824 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 4 ms 7988 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 6 ms 8120 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 5 ms 8116 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 7976 KB Output is correct
12 Correct 5 ms 8052 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 11 ms 21336 KB Output is correct
18 Correct 11 ms 21340 KB Output is correct
19 Correct 12 ms 21340 KB Output is correct
20 Correct 11 ms 21084 KB Output is correct
21 Incorrect 16 ms 20824 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 4 ms 7988 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 6 ms 8120 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 5 ms 8116 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 7976 KB Output is correct
12 Correct 5 ms 8052 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 11 ms 21336 KB Output is correct
18 Correct 11 ms 21340 KB Output is correct
19 Correct 12 ms 21340 KB Output is correct
20 Correct 11 ms 21084 KB Output is correct
21 Incorrect 16 ms 20824 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 295764 KB Output is correct
2 Correct 109 ms 251432 KB Output is correct
3 Correct 133 ms 295764 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 135 ms 295640 KB Output is correct
6 Correct 145 ms 295768 KB Output is correct
7 Correct 126 ms 295760 KB Output is correct
8 Correct 126 ms 295764 KB Output is correct
9 Correct 126 ms 295672 KB Output is correct
10 Correct 125 ms 295252 KB Output is correct
11 Correct 124 ms 295528 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 1208 KB Output is correct
3 Correct 4 ms 8044 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Incorrect 1152 ms 486664 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 4 ms 7988 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 6 ms 8120 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 5 ms 8116 KB Output is correct
10 Correct 4 ms 8028 KB Output is correct
11 Correct 4 ms 7976 KB Output is correct
12 Correct 5 ms 8052 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 11 ms 21336 KB Output is correct
18 Correct 11 ms 21340 KB Output is correct
19 Correct 12 ms 21340 KB Output is correct
20 Correct 11 ms 21084 KB Output is correct
21 Incorrect 16 ms 20824 KB Output isn't correct
22 Halted 0 ms 0 KB -