oj.uz

Submission #1008629

# Submission time Handle Problem Language Result Execution time Memory
1008629 2024-06-26T15:59:48 Z PagodePaiva Rectangles (IOI19_rect) C++17
72 / 100
 4965 ms 1048576 KB 
#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define int long long

using namespace std;

const int N = 2510;
const int inf = N;
int32_t v[N][N];
int p1[N][N];
int p2[N][N];
int p3[N][N];
int p4[N][N];

struct custom_hash {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

struct Segtree{
	int tree[4*N];
	int join(int a, int b){
		return min(a, b);
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = inf;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}	
	void update(int node, int l, int r, int pos, int val){
		if(l == r){
			tree[node] = val;
			return;
		}
		int mid = (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node+1, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		if(l <= tl and tr <= r) return tree[node];
		if(l > tr or tl > r) return inf;
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} seg1[N], seg3[N];

struct Segtree2{
	int tree[4*N];
	int join(int a, int b){
		return max(a, b);
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = -1;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}	
	void update(int node, int l, int r, int pos, int val){
		if(l == r){
			tree[node] = val;
			return;
		}
		int mid = (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node+1, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		if(l <= tl and tr <= r) return tree[node];
		if(l > tr or tl > r) return -1;
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} seg2[N], seg4[N];

unordered_set <int, custom_hash> 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(1,r1+1, r2-1, 1, n);
	if(c1+1 <= x1 and x1 <= c2-1) return false;
	x1 = seg2[c2].query(1, r1+1, r2-1, 1, n);
	if(c1 < x1 and x1 < c2) return false;
	int x2 = seg3[r1].query(1, c1+1, c2-1, 1, m);
	if(r1 < x2 and x2 < r2) return false;
	x2 = seg4[r2].query(1, c1+1, c2-1, 1, m);
	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) {
	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 <= m;i++){
		seg1[i].build(1, 1, n);
		seg2[i].build(1, 1, n);
	}
	for(int i = 1;i <= n;i++){
		seg3[i].build(1, 1, m);
		seg4[i].build(1, 1, m);
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			seg1[j].update(1, 1, n, i, p1[i][j]);
			seg2[j].update(1, 1, n, i, p2[i][j]);
			seg3[i].update(1, 1, m, j, p3[i][j]);
			seg4[i].update(1, 1, m, j, p4[i][j]);
		}
	}
	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(1, r1+1, r2-1, 1, n) : -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(1, c1+1, c2-1, 1, m) : -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(1, c1+1, c2-1, 1, m) : -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(1, r1+1, r2-1, 1, n) : -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(1, r1+1, r2-1, 1, n) : -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(1, c1+1, c2-1, 1, m) : -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(1, c1+1, c2-1, 1, m) : -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(1, r1+1, r2-1, 1, n) : -1);
			check(r1, c1, r2, c2);
			/*
			int c1 = p2[r2-1][c2];
			int r1 = p4[r2][c2-1];
			check(r1, c1, r2, c2);
			*/
		}
	}
	return s.size();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1640 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 648 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 440 KB Output is correct
19 Correct 1 ms 1628 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 0 ms 604 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1640 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 648 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 440 KB Output is correct
19 Correct 1 ms 1628 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 0 ms 604 KB Output is correct
22 Correct 5 ms 4444 KB Output is correct
23 Correct 7 ms 4444 KB Output is correct
24 Correct 7 ms 4440 KB Output is correct
25 Correct 4 ms 4188 KB Output is correct
26 Correct 5 ms 4188 KB Output is correct
27 Correct 5 ms 4324 KB Output is correct
28 Correct 5 ms 4188 KB Output is correct
29 Correct 3 ms 3404 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1640 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 648 KB Output is correct
17 Correct 5 ms 4444 KB Output is correct
18 Correct 7 ms 4444 KB Output is correct
19 Correct 7 ms 4440 KB Output is correct
20 Correct 4 ms 4188 KB Output is correct
21 Correct 5 ms 4188 KB Output is correct
22 Correct 5 ms 4324 KB Output is correct
23 Correct 5 ms 4188 KB Output is correct
24 Correct 3 ms 3404 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 440 KB Output is correct
27 Correct 1 ms 1628 KB Output is correct
28 Correct 1 ms 1372 KB Output is correct
29 Correct 0 ms 604 KB Output is correct
30 Correct 33 ms 14512 KB Output is correct
31 Correct 41 ms 14588 KB Output is correct
32 Correct 31 ms 14556 KB Output is correct
33 Correct 22 ms 12892 KB Output is correct
34 Correct 29 ms 13340 KB Output is correct
35 Correct 29 ms 13612 KB Output is correct
36 Correct 29 ms 13404 KB Output is correct
37 Correct 31 ms 13396 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1640 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 648 KB Output is correct
17 Correct 5 ms 4444 KB Output is correct
18 Correct 7 ms 4444 KB Output is correct
19 Correct 7 ms 4440 KB Output is correct
20 Correct 4 ms 4188 KB Output is correct
21 Correct 5 ms 4188 KB Output is correct
22 Correct 5 ms 4324 KB Output is correct
23 Correct 5 ms 4188 KB Output is correct
24 Correct 3 ms 3404 KB Output is correct
25 Correct 33 ms 14512 KB Output is correct
26 Correct 41 ms 14588 KB Output is correct
27 Correct 31 ms 14556 KB Output is correct
28 Correct 22 ms 12892 KB Output is correct
29 Correct 29 ms 13340 KB Output is correct
30 Correct 29 ms 13612 KB Output is correct
31 Correct 29 ms 13404 KB Output is correct
32 Correct 31 ms 13396 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 440 KB Output is correct
35 Correct 1 ms 1628 KB Output is correct
36 Correct 1 ms 1372 KB Output is correct
37 Correct 0 ms 604 KB Output is correct
38 Correct 254 ms 94600 KB Output is correct
39 Correct 234 ms 94792 KB Output is correct
40 Correct 241 ms 94756 KB Output is correct
41 Correct 234 ms 94804 KB Output is correct
42 Correct 528 ms 115720 KB Output is correct
43 Correct 570 ms 115536 KB Output is correct
44 Correct 627 ms 115880 KB Output is correct
45 Correct 529 ms 111064 KB Output is correct
46 Correct 307 ms 93660 KB Output is correct
47 Correct 366 ms 95152 KB Output is correct
48 Correct 485 ms 100032 KB Output is correct
49 Correct 499 ms 101916 KB Output is correct
50 Correct 240 ms 61024 KB Output is correct
51 Correct 220 ms 54108 KB Output is correct
52 Correct 495 ms 101312 KB Output is correct
53 Correct 494 ms 101824 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22364 KB Output is correct
2 Correct 10 ms 19140 KB Output is correct
3 Correct 9 ms 22312 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 12 ms 22156 KB Output is correct
6 Correct 11 ms 22360 KB Output is correct
7 Correct 11 ms 22364 KB Output is correct
8 Correct 12 ms 22324 KB Output is correct
9 Correct 11 ms 22364 KB Output is correct
10 Correct 9 ms 21444 KB Output is correct
11 Correct 10 ms 21592 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 2071 ms 477120 KB Output is correct
8 Correct 4643 ms 969196 KB Output is correct
9 Correct 4871 ms 972176 KB Output is correct
10 Correct 4965 ms 972464 KB Output is correct
11 Correct 928 ms 487276 KB Output is correct
12 Correct 1971 ms 936652 KB Output is correct
13 Correct 2011 ms 961616 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1640 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 648 KB Output is correct
17 Correct 5 ms 4444 KB Output is correct
18 Correct 7 ms 4444 KB Output is correct
19 Correct 7 ms 4440 KB Output is correct
20 Correct 4 ms 4188 KB Output is correct
21 Correct 5 ms 4188 KB Output is correct
22 Correct 5 ms 4324 KB Output is correct
23 Correct 5 ms 4188 KB Output is correct
24 Correct 3 ms 3404 KB Output is correct
25 Correct 33 ms 14512 KB Output is correct
26 Correct 41 ms 14588 KB Output is correct
27 Correct 31 ms 14556 KB Output is correct
28 Correct 22 ms 12892 KB Output is correct
29 Correct 29 ms 13340 KB Output is correct
30 Correct 29 ms 13612 KB Output is correct
31 Correct 29 ms 13404 KB Output is correct
32 Correct 31 ms 13396 KB Output is correct
33 Correct 254 ms 94600 KB Output is correct
34 Correct 234 ms 94792 KB Output is correct
35 Correct 241 ms 94756 KB Output is correct
36 Correct 234 ms 94804 KB Output is correct
37 Correct 528 ms 115720 KB Output is correct
38 Correct 570 ms 115536 KB Output is correct
39 Correct 627 ms 115880 KB Output is correct
40 Correct 529 ms 111064 KB Output is correct
41 Correct 307 ms 93660 KB Output is correct
42 Correct 366 ms 95152 KB Output is correct
43 Correct 485 ms 100032 KB Output is correct
44 Correct 499 ms 101916 KB Output is correct
45 Correct 240 ms 61024 KB Output is correct
46 Correct 220 ms 54108 KB Output is correct
47 Correct 495 ms 101312 KB Output is correct
48 Correct 494 ms 101824 KB Output is correct
49 Correct 11 ms 22364 KB Output is correct
50 Correct 10 ms 19140 KB Output is correct
51 Correct 9 ms 22312 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 12 ms 22156 KB Output is correct
54 Correct 11 ms 22360 KB Output is correct
55 Correct 11 ms 22364 KB Output is correct
56 Correct 12 ms 22324 KB Output is correct
57 Correct 11 ms 22364 KB Output is correct
58 Correct 9 ms 21444 KB Output is correct
59 Correct 10 ms 21592 KB Output is correct
60 Correct 1 ms 856 KB Output is correct
61 Correct 2071 ms 477120 KB Output is correct
62 Correct 4643 ms 969196 KB Output is correct
63 Correct 4871 ms 972176 KB Output is correct
64 Correct 4965 ms 972464 KB Output is correct
65 Correct 928 ms 487276 KB Output is correct
66 Correct 1971 ms 936652 KB Output is correct
67 Correct 2011 ms 961616 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 440 KB Output is correct
70 Correct 1 ms 1628 KB Output is correct
71 Correct 1 ms 1372 KB Output is correct
72 Correct 0 ms 604 KB Output is correct
73 Correct 3785 ms 991876 KB Output is correct
74 Correct 3677 ms 991768 KB Output is correct
75 Correct 3489 ms 991932 KB Output is correct
76 Correct 3619 ms 995924 KB Output is correct
77 Runtime error 4375 ms 1048576 KB Execution killed with signal 9
78 Halted 0 ms 0 KB -