oj.uz

Submission #1064750

# Submission time Handle Problem Language Result Execution time Memory
1064750 2024-08-18T17:24:57 Z jamjanek Rectangles (IOI19_rect) C++14
100 / 100
 4623 ms 721172 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;
	return MAXI1(1, 0, base-1, l, r, war);
	for(int i=l;i<=r;i++)
		res = max(res, nast2[i][war][0]);
	return res;
}
int mini1(int war, int l, int r){
	return MINI1(1, 0, base-1, l, r, war);
	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast2[i][war][1]);
	return res;
}
int maxi2(int war, int l, int r){
	return MAXI2(1, 0, base-1, l, r, war);
	int res = -1;
	for(int i=l;i<=r;i++)
		res = max(res, nast2[war][i][2]);
	return res;
}
int mini2(int war, int l, int r){
	return MINI2(1, 0, base-1, l, r, war);
	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast2[war][i][3]);
	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 10 ms 71516 KB Output is correct
2 Correct 13 ms 74332 KB Output is correct
3 Correct 12 ms 75544 KB Output is correct
4 Correct 14 ms 74332 KB Output is correct
5 Correct 13 ms 74328 KB Output is correct
6 Correct 12 ms 75612 KB Output is correct
7 Correct 12 ms 76376 KB Output is correct
8 Correct 11 ms 75816 KB Output is correct
9 Correct 12 ms 77912 KB Output is correct
10 Correct 12 ms 76636 KB Output is correct
11 Correct 13 ms 76636 KB Output is correct
12 Correct 12 ms 76636 KB Output is correct
13 Correct 9 ms 73816 KB Output is correct
14 Correct 10 ms 74584 KB Output is correct
15 Correct 10 ms 74840 KB Output is correct
16 Correct 9 ms 73820 KB Output is correct
17 Correct 9 ms 73816 KB Output is correct
18 Correct 10 ms 73816 KB Output is correct
19 Correct 15 ms 76632 KB Output is correct
20 Correct 13 ms 76636 KB Output is correct
21 Correct 9 ms 74588 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 71516 KB Output is correct
2 Correct 13 ms 74332 KB Output is correct
3 Correct 12 ms 75544 KB Output is correct
4 Correct 14 ms 74332 KB Output is correct
5 Correct 13 ms 74328 KB Output is correct
6 Correct 12 ms 75612 KB Output is correct
7 Correct 12 ms 76376 KB Output is correct
8 Correct 11 ms 75816 KB Output is correct
9 Correct 12 ms 77912 KB Output is correct
10 Correct 12 ms 76636 KB Output is correct
11 Correct 13 ms 76636 KB Output is correct
12 Correct 12 ms 76636 KB Output is correct
13 Correct 9 ms 73816 KB Output is correct
14 Correct 10 ms 74584 KB Output is correct
15 Correct 10 ms 74840 KB Output is correct
16 Correct 9 ms 73820 KB Output is correct
17 Correct 9 ms 73816 KB Output is correct
18 Correct 10 ms 73816 KB Output is correct
19 Correct 15 ms 76632 KB Output is correct
20 Correct 13 ms 76636 KB Output is correct
21 Correct 9 ms 74588 KB Output is correct
22 Correct 19 ms 81500 KB Output is correct
23 Correct 21 ms 82596 KB Output is correct
24 Correct 21 ms 81500 KB Output is correct
25 Correct 20 ms 81244 KB Output is correct
26 Correct 18 ms 81260 KB Output is correct
27 Correct 19 ms 82524 KB Output is correct
28 Correct 18 ms 81408 KB Output is correct
29 Correct 16 ms 80472 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 71516 KB Output is correct
2 Correct 13 ms 74332 KB Output is correct
3 Correct 12 ms 75544 KB Output is correct
4 Correct 14 ms 74332 KB Output is correct
5 Correct 13 ms 74328 KB Output is correct
6 Correct 12 ms 75612 KB Output is correct
7 Correct 12 ms 76376 KB Output is correct
8 Correct 11 ms 75816 KB Output is correct
9 Correct 12 ms 77912 KB Output is correct
10 Correct 12 ms 76636 KB Output is correct
11 Correct 13 ms 76636 KB Output is correct
12 Correct 12 ms 76636 KB Output is correct
13 Correct 9 ms 73816 KB Output is correct
14 Correct 10 ms 74584 KB Output is correct
15 Correct 10 ms 74840 KB Output is correct
16 Correct 9 ms 73820 KB Output is correct
17 Correct 19 ms 81500 KB Output is correct
18 Correct 21 ms 82596 KB Output is correct
19 Correct 21 ms 81500 KB Output is correct
20 Correct 20 ms 81244 KB Output is correct
21 Correct 18 ms 81260 KB Output is correct
22 Correct 19 ms 82524 KB Output is correct
23 Correct 18 ms 81408 KB Output is correct
24 Correct 16 ms 80472 KB Output is correct
25 Correct 9 ms 73816 KB Output is correct
26 Correct 10 ms 73816 KB Output is correct
27 Correct 15 ms 76632 KB Output is correct
28 Correct 13 ms 76636 KB Output is correct
29 Correct 9 ms 74588 KB Output is correct
30 Correct 50 ms 93648 KB Output is correct
31 Correct 48 ms 93692 KB Output is correct
32 Correct 48 ms 93900 KB Output is correct
33 Correct 39 ms 93128 KB Output is correct
34 Correct 42 ms 93132 KB Output is correct
35 Correct 44 ms 94412 KB Output is correct
36 Correct 45 ms 93464 KB Output is correct
37 Correct 42 ms 93396 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 71516 KB Output is correct
2 Correct 13 ms 74332 KB Output is correct
3 Correct 12 ms 75544 KB Output is correct
4 Correct 14 ms 74332 KB Output is correct
5 Correct 13 ms 74328 KB Output is correct
6 Correct 12 ms 75612 KB Output is correct
7 Correct 12 ms 76376 KB Output is correct
8 Correct 11 ms 75816 KB Output is correct
9 Correct 12 ms 77912 KB Output is correct
10 Correct 12 ms 76636 KB Output is correct
11 Correct 13 ms 76636 KB Output is correct
12 Correct 12 ms 76636 KB Output is correct
13 Correct 9 ms 73816 KB Output is correct
14 Correct 10 ms 74584 KB Output is correct
15 Correct 10 ms 74840 KB Output is correct
16 Correct 9 ms 73820 KB Output is correct
17 Correct 19 ms 81500 KB Output is correct
18 Correct 21 ms 82596 KB Output is correct
19 Correct 21 ms 81500 KB Output is correct
20 Correct 20 ms 81244 KB Output is correct
21 Correct 18 ms 81260 KB Output is correct
22 Correct 19 ms 82524 KB Output is correct
23 Correct 18 ms 81408 KB Output is correct
24 Correct 16 ms 80472 KB Output is correct
25 Correct 50 ms 93648 KB Output is correct
26 Correct 48 ms 93692 KB Output is correct
27 Correct 48 ms 93900 KB Output is correct
28 Correct 39 ms 93128 KB Output is correct
29 Correct 42 ms 93132 KB Output is correct
30 Correct 44 ms 94412 KB Output is correct
31 Correct 45 ms 93464 KB Output is correct
32 Correct 42 ms 93396 KB Output is correct
33 Correct 9 ms 73816 KB Output is correct
34 Correct 10 ms 73816 KB Output is correct
35 Correct 15 ms 76632 KB Output is correct
36 Correct 13 ms 76636 KB Output is correct
37 Correct 9 ms 74588 KB Output is correct
38 Correct 141 ms 171924 KB Output is correct
39 Correct 140 ms 171720 KB Output is correct
40 Correct 149 ms 171936 KB Output is correct
41 Correct 138 ms 171748 KB Output is correct
42 Correct 396 ms 181084 KB Output is correct
43 Correct 381 ms 180884 KB Output is correct
44 Correct 381 ms 181388 KB Output is correct
45 Correct 368 ms 173384 KB Output is correct
46 Correct 203 ms 171908 KB Output is correct
47 Correct 230 ms 172728 KB Output is correct
48 Correct 303 ms 173824 KB Output is correct
49 Correct 296 ms 175784 KB Output is correct
50 Correct 170 ms 149820 KB Output is correct
51 Correct 173 ms 126372 KB Output is correct
52 Correct 280 ms 175028 KB Output is correct
53 Correct 302 ms 176024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 91136 KB Output is correct
2 Correct 115 ms 91096 KB Output is correct
3 Correct 148 ms 90964 KB Output is correct
4 Correct 13 ms 67676 KB Output is correct
5 Correct 116 ms 90956 KB Output is correct
6 Correct 122 ms 90960 KB Output is correct
7 Correct 111 ms 90956 KB Output is correct
8 Correct 102 ms 90964 KB Output is correct
9 Correct 109 ms 90920 KB Output is correct
10 Correct 124 ms 90792 KB Output is correct
11 Correct 115 ms 90924 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 73816 KB Output is correct
2 Correct 10 ms 73816 KB Output is correct
3 Correct 15 ms 76632 KB Output is correct
4 Correct 13 ms 76636 KB Output is correct
5 Correct 9 ms 74588 KB Output is correct
6 Correct 11 ms 74744 KB Output is correct
7 Correct 989 ms 350796 KB Output is correct
8 Correct 1839 ms 609376 KB Output is correct
9 Correct 1901 ms 611244 KB Output is correct
10 Correct 1818 ms 611224 KB Output is correct
11 Correct 526 ms 345532 KB Output is correct
12 Correct 900 ms 580508 KB Output is correct
13 Correct 913 ms 586472 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 71516 KB Output is correct
2 Correct 13 ms 74332 KB Output is correct
3 Correct 12 ms 75544 KB Output is correct
4 Correct 14 ms 74332 KB Output is correct
5 Correct 13 ms 74328 KB Output is correct
6 Correct 12 ms 75612 KB Output is correct
7 Correct 12 ms 76376 KB Output is correct
8 Correct 11 ms 75816 KB Output is correct
9 Correct 12 ms 77912 KB Output is correct
10 Correct 12 ms 76636 KB Output is correct
11 Correct 13 ms 76636 KB Output is correct
12 Correct 12 ms 76636 KB Output is correct
13 Correct 9 ms 73816 KB Output is correct
14 Correct 10 ms 74584 KB Output is correct
15 Correct 10 ms 74840 KB Output is correct
16 Correct 9 ms 73820 KB Output is correct
17 Correct 19 ms 81500 KB Output is correct
18 Correct 21 ms 82596 KB Output is correct
19 Correct 21 ms 81500 KB Output is correct
20 Correct 20 ms 81244 KB Output is correct
21 Correct 18 ms 81260 KB Output is correct
22 Correct 19 ms 82524 KB Output is correct
23 Correct 18 ms 81408 KB Output is correct
24 Correct 16 ms 80472 KB Output is correct
25 Correct 50 ms 93648 KB Output is correct
26 Correct 48 ms 93692 KB Output is correct
27 Correct 48 ms 93900 KB Output is correct
28 Correct 39 ms 93128 KB Output is correct
29 Correct 42 ms 93132 KB Output is correct
30 Correct 44 ms 94412 KB Output is correct
31 Correct 45 ms 93464 KB Output is correct
32 Correct 42 ms 93396 KB Output is correct
33 Correct 141 ms 171924 KB Output is correct
34 Correct 140 ms 171720 KB Output is correct
35 Correct 149 ms 171936 KB Output is correct
36 Correct 138 ms 171748 KB Output is correct
37 Correct 396 ms 181084 KB Output is correct
38 Correct 381 ms 180884 KB Output is correct
39 Correct 381 ms 181388 KB Output is correct
40 Correct 368 ms 173384 KB Output is correct
41 Correct 203 ms 171908 KB Output is correct
42 Correct 230 ms 172728 KB Output is correct
43 Correct 303 ms 173824 KB Output is correct
44 Correct 296 ms 175784 KB Output is correct
45 Correct 170 ms 149820 KB Output is correct
46 Correct 173 ms 126372 KB Output is correct
47 Correct 280 ms 175028 KB Output is correct
48 Correct 302 ms 176024 KB Output is correct
49 Correct 123 ms 91136 KB Output is correct
50 Correct 115 ms 91096 KB Output is correct
51 Correct 148 ms 90964 KB Output is correct
52 Correct 13 ms 67676 KB Output is correct
53 Correct 116 ms 90956 KB Output is correct
54 Correct 122 ms 90960 KB Output is correct
55 Correct 111 ms 90956 KB Output is correct
56 Correct 102 ms 90964 KB Output is correct
57 Correct 109 ms 90920 KB Output is correct
58 Correct 124 ms 90792 KB Output is correct
59 Correct 115 ms 90924 KB Output is correct
60 Correct 11 ms 74744 KB Output is correct
61 Correct 989 ms 350796 KB Output is correct
62 Correct 1839 ms 609376 KB Output is correct
63 Correct 1901 ms 611244 KB Output is correct
64 Correct 1818 ms 611224 KB Output is correct
65 Correct 526 ms 345532 KB Output is correct
66 Correct 900 ms 580508 KB Output is correct
67 Correct 913 ms 586472 KB Output is correct
68 Correct 9 ms 73816 KB Output is correct
69 Correct 10 ms 73816 KB Output is correct
70 Correct 15 ms 76632 KB Output is correct
71 Correct 13 ms 76636 KB Output is correct
72 Correct 9 ms 74588 KB Output is correct
73 Correct 1056 ms 603064 KB Output is correct
74 Correct 1093 ms 603308 KB Output is correct
75 Correct 1035 ms 603156 KB Output is correct
76 Correct 1041 ms 603092 KB Output is correct
77 Correct 4623 ms 712872 KB Output is correct
78 Correct 1946 ms 416816 KB Output is correct
79 Correct 2088 ms 525520 KB Output is correct
80 Correct 3187 ms 636456 KB Output is correct
81 Correct 2009 ms 431948 KB Output is correct
82 Correct 2687 ms 609108 KB Output is correct
83 Correct 3302 ms 661820 KB Output is correct
84 Correct 1845 ms 426176 KB Output is correct
85 Correct 3180 ms 664128 KB Output is correct
86 Correct 3038 ms 649860 KB Output is correct
87 Correct 2692 ms 574772 KB Output is correct
88 Correct 4388 ms 720716 KB Output is correct
89 Correct 4429 ms 720996 KB Output is correct
90 Correct 4329 ms 721172 KB Output is correct