oj.uz

Submission #1064762

# Submission time Handle Problem Language Result Execution time Memory
1064762 2024-08-18T17:29:58 Z jamjanek Rectangles (IOI19_rect) C++14
100 / 100
 2905 ms 697756 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>stosy[2510];
int nast[2510][2510][4];
int nast2[2510][2510][4];

const int base = 1<<12;
int tree1[2510][2*base];
int tree2[2510][2*base];
int tree3[2*base][2510];
int tree4[2*base][2510];

int MAXI1(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return -1;
	if(a<=l && p<=b)return tree3[w][war];
	return max(MAXI1(w*2, l, (l+p)/2, a, b, war), MAXI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI1(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return 2600;
	if(a<=l && p<=b)return tree4[w][war];
	return min(MINI1(w*2, l, (l+p)/2, a, b, war), MINI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MAXI2(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return -1;
	if(a<=l && p<=b)return tree1[war][w];
	return max(MAXI2(w*2, l, (l+p)/2, a, b, war), MAXI2(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI2(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return 2600;
	if(a<=l && p<=b)return tree2[war][w];
	return min(MINI2(w*2, l, (l+p)/2, a, b, war), MINI2(w*2+1, (l+p)/2+1, p, a, b, war));
}

int maxi1(int war, int l, int r){
//	printf("%d %d %d  ", war, l, r);
	l+=base, r+=base;
	if(l>r)return -1;
	int res = max(tree3[l][war], tree3[r][war]);
	while(l/2<r/2){
		if((l&1)==0){
			res = max(res, tree3[l^1][war]);
		}
		if(r&1){
			res = max(res, tree3[r^1][war]);
		}
		l>>=1;
		r>>=1;
	}
//	printf("%d\n", res);
	return res;
}
int mini1(int war, int l, int r){
	l+=base, r+=base;
	if(l>r)return 2600;
	int res = min(tree4[l][war], tree4[r][war]);
	while(l/2<r/2){
		if((l&1)==0){
			res = min(res, tree4[l^1][war]);
		}
		if(r&1){
			res = min(res, tree4[r^1][war]);
		}
		l>>=1;
		r>>=1;
	}
//	printf("%d\n", res);
	return res;

	return MINI1(1, 0, base-1, l, r, war);
}
int maxi2(int war, int l, int r){
	l+=base, r+=base;
	if(l>r)return -1;
	int res = max(tree1[war][l], tree1[war][r]);
	while(l/2<r/2){
		if((l&1)==0){
			res = max(res, tree1[war][l^1]);
		}
		if(r&1){
			res = max(res, tree1[war][r^1]);
		}
		l>>=1;
		r>>=1;
	}
//	printf("%d\n", res);
	return res;
}
int mini2(int war, int l, int r){
	l+=base, r+=base;
	if(l>r)return 2600;
	int res = min(tree2[war][l], tree2[war][r]);
	while(l/2<r/2){
		if((l&1)==0){
			res = min(res, tree2[war][l^1]);
		}
		if(r&1){
			res = min(res, tree2[war][r^1]);
		}
		l>>=1;
		r>>=1;
	}
//	printf("%d\n", res);
	return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	int i, j;

	//poprzednie po x [0]	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][0] = stosy[i].back().second;
			else
				nast[i][j][0] = -1;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();

	//nastepne po x [1]

	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][1] = stosy[i].back().second;
			else
				nast[i][j][1] = m;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();
	
	//poprzednie po y [2]
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][2] = stosy[i].back().second;
			else
				nast[j][i][2] = -1;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	//nastepne po y [3]
	for(i=0;i<m;i++){
		for(j = n-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][3] = stosy[i].back().second;
			else
				nast[j][i][3] = n;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();
		
		
		
		
		
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			while(stosy[i].size() && stosy[i].back().first<a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[i][j][0] = stosy[i].back().second;
			else
				nast2[i][j][0] = -1;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();

	//nastepne po x [1]

	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[i][j][1] = stosy[i].back().second;
			else
				nast2[i][j][1] = m;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();
	
	//poprzednie po y [2]
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			while(stosy[i].size() && stosy[i].back().first<a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[j][i][2] = stosy[i].back().second;
			else
				nast2[j][i][2] = -1;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	//nastepne po y [3]
	for(i=0;i<m;i++){
		for(j = n-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[j][i][3] = stosy[i].back().second;
			else
				nast2[j][i][3] = n;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();



	vector<pair<pair<int,int>, pair<int,int>>>sett;
	for(i=1;i<n-1;i++)
		for(j=1;j<m-1;j++){
			//printf("%d %d %d %d\n", nast[i][j][0], nast[i][j][1], nast[i][j][2], nast[i][j][3]);
			if(nast[i][j][0]!=-1 && nast[i][j][1]!=m && nast[i][j][2]!=-1 && nast[i][j][3]!=n){
				//printf("dodaje\n");
				sett.push_back({{nast[i][j][0], nast[i][j][1]}, {nast[i][j][2], nast[i][j][3]}});
			}
		}
	
	for(i=0;i<n;i++)
		for(j=0;j<m;j++){
			tree3[base+i][j] = nast2[i][j][0];
			tree4[base+i][j] = nast2[i][j][1];
			tree1[i][base+j] = nast2[i][j][2];
			tree2[i][base+j] = nast2[i][j][3];
		}
	for(i=0;i<n;i++)
		for(j=base-1;j>0;j--){
			tree1[i][j] = max(tree1[i][j*2], tree1[i][j*2+1]);
			tree2[i][j] = min(tree2[i][j*2], tree2[i][j*2+1]);
		}
	for(i=0;i<m;i++)
		for(j=base-1;j>0;j--){
			tree3[j][i] = max(tree3[j*2][i], tree3[j*2+1][i]);
			tree4[j][i] = min(tree4[j*2][i], tree4[j*2+1][i]);
		}
	sort(sett.begin(), sett.end());
	long long wynik = 0;
	for(i=0;i<(int)sett.size();i++){
		if(i!=0 && sett[i-1]==sett[i])continue;
		auto x = sett[i];
		if(mini1(x.first.first, x.second.first+1, x.second.second-1)<x.first.second)continue;
		if(maxi1(x.first.second, x.second.first+1, x.second.second-1)>x.first.first)continue;

		if(mini2(x.second.first, x.first.first+1, x.first.second-1)<x.second.second)continue;
		if(maxi2(x.second.second, x.first.first+1, x.first.second-1)>x.second.first)continue;
		wynik++;
	}
	
	return wynik;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 61784 KB Output is correct
2 Correct 13 ms 64860 KB Output is correct
3 Correct 14 ms 64884 KB Output is correct
4 Correct 14 ms 64856 KB Output is correct
5 Correct 15 ms 64856 KB Output is correct
6 Correct 13 ms 64828 KB Output is correct
7 Correct 12 ms 65628 KB Output is correct
8 Correct 13 ms 63832 KB Output is correct
9 Correct 14 ms 64860 KB Output is correct
10 Correct 13 ms 66140 KB Output is correct
11 Correct 14 ms 64956 KB Output is correct
12 Correct 13 ms 64856 KB Output is correct
13 Correct 10 ms 61744 KB Output is correct
14 Correct 11 ms 62616 KB Output is correct
15 Correct 11 ms 63832 KB Output is correct
16 Correct 11 ms 61808 KB Output is correct
17 Correct 10 ms 61784 KB Output is correct
18 Correct 11 ms 61788 KB Output is correct
19 Correct 13 ms 64856 KB Output is correct
20 Correct 13 ms 64572 KB Output is correct
21 Correct 11 ms 62552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 61784 KB Output is correct
2 Correct 13 ms 64860 KB Output is correct
3 Correct 14 ms 64884 KB Output is correct
4 Correct 14 ms 64856 KB Output is correct
5 Correct 15 ms 64856 KB Output is correct
6 Correct 13 ms 64828 KB Output is correct
7 Correct 12 ms 65628 KB Output is correct
8 Correct 13 ms 63832 KB Output is correct
9 Correct 14 ms 64860 KB Output is correct
10 Correct 13 ms 66140 KB Output is correct
11 Correct 14 ms 64956 KB Output is correct
12 Correct 13 ms 64856 KB Output is correct
13 Correct 10 ms 61744 KB Output is correct
14 Correct 11 ms 62616 KB Output is correct
15 Correct 11 ms 63832 KB Output is correct
16 Correct 11 ms 61808 KB Output is correct
17 Correct 10 ms 61784 KB Output is correct
18 Correct 11 ms 61788 KB Output is correct
19 Correct 13 ms 64856 KB Output is correct
20 Correct 13 ms 64572 KB Output is correct
21 Correct 11 ms 62552 KB Output is correct
22 Correct 19 ms 71000 KB Output is correct
23 Correct 19 ms 69968 KB Output is correct
24 Correct 20 ms 70992 KB Output is correct
25 Correct 19 ms 69724 KB Output is correct
26 Correct 19 ms 69724 KB Output is correct
27 Correct 19 ms 69724 KB Output is correct
28 Correct 19 ms 69724 KB Output is correct
29 Correct 16 ms 68700 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 61784 KB Output is correct
2 Correct 13 ms 64860 KB Output is correct
3 Correct 14 ms 64884 KB Output is correct
4 Correct 14 ms 64856 KB Output is correct
5 Correct 15 ms 64856 KB Output is correct
6 Correct 13 ms 64828 KB Output is correct
7 Correct 12 ms 65628 KB Output is correct
8 Correct 13 ms 63832 KB Output is correct
9 Correct 14 ms 64860 KB Output is correct
10 Correct 13 ms 66140 KB Output is correct
11 Correct 14 ms 64956 KB Output is correct
12 Correct 13 ms 64856 KB Output is correct
13 Correct 10 ms 61744 KB Output is correct
14 Correct 11 ms 62616 KB Output is correct
15 Correct 11 ms 63832 KB Output is correct
16 Correct 11 ms 61808 KB Output is correct
17 Correct 19 ms 71000 KB Output is correct
18 Correct 19 ms 69968 KB Output is correct
19 Correct 20 ms 70992 KB Output is correct
20 Correct 19 ms 69724 KB Output is correct
21 Correct 19 ms 69724 KB Output is correct
22 Correct 19 ms 69724 KB Output is correct
23 Correct 19 ms 69724 KB Output is correct
24 Correct 16 ms 68700 KB Output is correct
25 Correct 10 ms 61784 KB Output is correct
26 Correct 11 ms 61788 KB Output is correct
27 Correct 13 ms 64856 KB Output is correct
28 Correct 13 ms 64572 KB Output is correct
29 Correct 11 ms 62552 KB Output is correct
30 Correct 41 ms 82632 KB Output is correct
31 Correct 41 ms 82632 KB Output is correct
32 Correct 42 ms 82888 KB Output is correct
33 Correct 38 ms 82128 KB Output is correct
34 Correct 40 ms 82388 KB Output is correct
35 Correct 41 ms 82404 KB Output is correct
36 Correct 41 ms 82412 KB Output is correct
37 Correct 40 ms 82228 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 61784 KB Output is correct
2 Correct 13 ms 64860 KB Output is correct
3 Correct 14 ms 64884 KB Output is correct
4 Correct 14 ms 64856 KB Output is correct
5 Correct 15 ms 64856 KB Output is correct
6 Correct 13 ms 64828 KB Output is correct
7 Correct 12 ms 65628 KB Output is correct
8 Correct 13 ms 63832 KB Output is correct
9 Correct 14 ms 64860 KB Output is correct
10 Correct 13 ms 66140 KB Output is correct
11 Correct 14 ms 64956 KB Output is correct
12 Correct 13 ms 64856 KB Output is correct
13 Correct 10 ms 61744 KB Output is correct
14 Correct 11 ms 62616 KB Output is correct
15 Correct 11 ms 63832 KB Output is correct
16 Correct 11 ms 61808 KB Output is correct
17 Correct 19 ms 71000 KB Output is correct
18 Correct 19 ms 69968 KB Output is correct
19 Correct 20 ms 70992 KB Output is correct
20 Correct 19 ms 69724 KB Output is correct
21 Correct 19 ms 69724 KB Output is correct
22 Correct 19 ms 69724 KB Output is correct
23 Correct 19 ms 69724 KB Output is correct
24 Correct 16 ms 68700 KB Output is correct
25 Correct 41 ms 82632 KB Output is correct
26 Correct 41 ms 82632 KB Output is correct
27 Correct 42 ms 82888 KB Output is correct
28 Correct 38 ms 82128 KB Output is correct
29 Correct 40 ms 82388 KB Output is correct
30 Correct 41 ms 82404 KB Output is correct
31 Correct 41 ms 82412 KB Output is correct
32 Correct 40 ms 82228 KB Output is correct
33 Correct 10 ms 61784 KB Output is correct
34 Correct 11 ms 61788 KB Output is correct
35 Correct 13 ms 64856 KB Output is correct
36 Correct 13 ms 64572 KB Output is correct
37 Correct 11 ms 62552 KB Output is correct
38 Correct 137 ms 158548 KB Output is correct
39 Correct 136 ms 158544 KB Output is correct
40 Correct 135 ms 158548 KB Output is correct
41 Correct 135 ms 158548 KB Output is correct
42 Correct 254 ms 168796 KB Output is correct
43 Correct 252 ms 167592 KB Output is correct
44 Correct 260 ms 167868 KB Output is correct
45 Correct 242 ms 162900 KB Output is correct
46 Correct 169 ms 158656 KB Output is correct
47 Correct 187 ms 158900 KB Output is correct
48 Correct 219 ms 160564 KB Output is correct
49 Correct 224 ms 163500 KB Output is correct
50 Correct 132 ms 133564 KB Output is correct
51 Correct 142 ms 120548 KB Output is correct
52 Correct 217 ms 161712 KB Output is correct
53 Correct 228 ms 162504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 90964 KB Output is correct
2 Correct 110 ms 91116 KB Output is correct
3 Correct 128 ms 90980 KB Output is correct
4 Correct 11 ms 61784 KB Output is correct
5 Correct 129 ms 90964 KB Output is correct
6 Correct 132 ms 90960 KB Output is correct
7 Correct 132 ms 90840 KB Output is correct
8 Correct 139 ms 90768 KB Output is correct
9 Correct 130 ms 90956 KB Output is correct
10 Correct 129 ms 90712 KB Output is correct
11 Correct 136 ms 90760 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 61784 KB Output is correct
2 Correct 11 ms 61788 KB Output is correct
3 Correct 13 ms 64856 KB Output is correct
4 Correct 13 ms 64572 KB Output is correct
5 Correct 11 ms 62552 KB Output is correct
6 Correct 11 ms 62556 KB Output is correct
7 Correct 783 ms 348608 KB Output is correct
8 Correct 1475 ms 609864 KB Output is correct
9 Correct 1521 ms 611800 KB Output is correct
10 Correct 1521 ms 611956 KB Output is correct
11 Correct 539 ms 342868 KB Output is correct
12 Correct 861 ms 580692 KB Output is correct
13 Correct 935 ms 587400 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 61784 KB Output is correct
2 Correct 13 ms 64860 KB Output is correct
3 Correct 14 ms 64884 KB Output is correct
4 Correct 14 ms 64856 KB Output is correct
5 Correct 15 ms 64856 KB Output is correct
6 Correct 13 ms 64828 KB Output is correct
7 Correct 12 ms 65628 KB Output is correct
8 Correct 13 ms 63832 KB Output is correct
9 Correct 14 ms 64860 KB Output is correct
10 Correct 13 ms 66140 KB Output is correct
11 Correct 14 ms 64956 KB Output is correct
12 Correct 13 ms 64856 KB Output is correct
13 Correct 10 ms 61744 KB Output is correct
14 Correct 11 ms 62616 KB Output is correct
15 Correct 11 ms 63832 KB Output is correct
16 Correct 11 ms 61808 KB Output is correct
17 Correct 19 ms 71000 KB Output is correct
18 Correct 19 ms 69968 KB Output is correct
19 Correct 20 ms 70992 KB Output is correct
20 Correct 19 ms 69724 KB Output is correct
21 Correct 19 ms 69724 KB Output is correct
22 Correct 19 ms 69724 KB Output is correct
23 Correct 19 ms 69724 KB Output is correct
24 Correct 16 ms 68700 KB Output is correct
25 Correct 41 ms 82632 KB Output is correct
26 Correct 41 ms 82632 KB Output is correct
27 Correct 42 ms 82888 KB Output is correct
28 Correct 38 ms 82128 KB Output is correct
29 Correct 40 ms 82388 KB Output is correct
30 Correct 41 ms 82404 KB Output is correct
31 Correct 41 ms 82412 KB Output is correct
32 Correct 40 ms 82228 KB Output is correct
33 Correct 137 ms 158548 KB Output is correct
34 Correct 136 ms 158544 KB Output is correct
35 Correct 135 ms 158548 KB Output is correct
36 Correct 135 ms 158548 KB Output is correct
37 Correct 254 ms 168796 KB Output is correct
38 Correct 252 ms 167592 KB Output is correct
39 Correct 260 ms 167868 KB Output is correct
40 Correct 242 ms 162900 KB Output is correct
41 Correct 169 ms 158656 KB Output is correct
42 Correct 187 ms 158900 KB Output is correct
43 Correct 219 ms 160564 KB Output is correct
44 Correct 224 ms 163500 KB Output is correct
45 Correct 132 ms 133564 KB Output is correct
46 Correct 142 ms 120548 KB Output is correct
47 Correct 217 ms 161712 KB Output is correct
48 Correct 228 ms 162504 KB Output is correct
49 Correct 151 ms 90964 KB Output is correct
50 Correct 110 ms 91116 KB Output is correct
51 Correct 128 ms 90980 KB Output is correct
52 Correct 11 ms 61784 KB Output is correct
53 Correct 129 ms 90964 KB Output is correct
54 Correct 132 ms 90960 KB Output is correct
55 Correct 132 ms 90840 KB Output is correct
56 Correct 139 ms 90768 KB Output is correct
57 Correct 130 ms 90956 KB Output is correct
58 Correct 129 ms 90712 KB Output is correct
59 Correct 136 ms 90760 KB Output is correct
60 Correct 11 ms 62556 KB Output is correct
61 Correct 783 ms 348608 KB Output is correct
62 Correct 1475 ms 609864 KB Output is correct
63 Correct 1521 ms 611800 KB Output is correct
64 Correct 1521 ms 611956 KB Output is correct
65 Correct 539 ms 342868 KB Output is correct
66 Correct 861 ms 580692 KB Output is correct
67 Correct 935 ms 587400 KB Output is correct
68 Correct 10 ms 61784 KB Output is correct
69 Correct 11 ms 61788 KB Output is correct
70 Correct 13 ms 64856 KB Output is correct
71 Correct 13 ms 64572 KB Output is correct
72 Correct 11 ms 62552 KB Output is correct
73 Correct 1042 ms 605920 KB Output is correct
74 Correct 1042 ms 585388 KB Output is correct
75 Correct 1043 ms 585292 KB Output is correct
76 Correct 1054 ms 585200 KB Output is correct
77 Correct 2817 ms 697756 KB Output is correct
78 Correct 1357 ms 409388 KB Output is correct
79 Correct 1430 ms 509420 KB Output is correct
80 Correct 2222 ms 625492 KB Output is correct
81 Correct 1418 ms 417004 KB Output is correct
82 Correct 1858 ms 588176 KB Output is correct
83 Correct 2476 ms 638196 KB Output is correct
84 Correct 1382 ms 414996 KB Output is correct
85 Correct 2279 ms 640608 KB Output is correct
86 Correct 2175 ms 626688 KB Output is correct
87 Correct 1729 ms 560988 KB Output is correct
88 Correct 2799 ms 697232 KB Output is correct
89 Correct 2905 ms 697528 KB Output is correct
90 Correct 2863 ms 697376 KB Output is correct