oj.uz

Submission #1064657

# Submission time Handle Problem Language Result Execution time Memory
1064657 2024-08-18T16:31:28 Z jamjanek Rectangles (IOI19_rect) C++14
72 / 100
 3724 ms 1048576 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<<13;
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){
	return MAXI1(1, 0, base-1, l, r, war);
	int res = -1;
	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();



	set<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.insert({{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]);
		}
	long long wynik = 0;
	for(auto x: sett){
		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 23 ms 91732 KB Output is correct
2 Correct 32 ms 96552 KB Output is correct
3 Correct 30 ms 96500 KB Output is correct
4 Correct 30 ms 96464 KB Output is correct
5 Correct 31 ms 96480 KB Output is correct
6 Correct 29 ms 96604 KB Output is correct
7 Correct 25 ms 95568 KB Output is correct
8 Correct 30 ms 94084 KB Output is correct
9 Correct 38 ms 96688 KB Output is correct
10 Correct 28 ms 96548 KB Output is correct
11 Correct 37 ms 96592 KB Output is correct
12 Correct 27 ms 96592 KB Output is correct
13 Correct 26 ms 91552 KB Output is correct
14 Correct 23 ms 92508 KB Output is correct
15 Correct 25 ms 92888 KB Output is correct
16 Correct 27 ms 91740 KB Output is correct
17 Correct 22 ms 91484 KB Output is correct
18 Correct 26 ms 91844 KB Output is correct
19 Correct 31 ms 96604 KB Output is correct
20 Correct 29 ms 95824 KB Output is correct
21 Correct 26 ms 92500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 91732 KB Output is correct
2 Correct 32 ms 96552 KB Output is correct
3 Correct 30 ms 96500 KB Output is correct
4 Correct 30 ms 96464 KB Output is correct
5 Correct 31 ms 96480 KB Output is correct
6 Correct 29 ms 96604 KB Output is correct
7 Correct 25 ms 95568 KB Output is correct
8 Correct 30 ms 94084 KB Output is correct
9 Correct 38 ms 96688 KB Output is correct
10 Correct 28 ms 96548 KB Output is correct
11 Correct 37 ms 96592 KB Output is correct
12 Correct 27 ms 96592 KB Output is correct
13 Correct 26 ms 91552 KB Output is correct
14 Correct 23 ms 92508 KB Output is correct
15 Correct 25 ms 92888 KB Output is correct
16 Correct 27 ms 91740 KB Output is correct
17 Correct 22 ms 91484 KB Output is correct
18 Correct 26 ms 91844 KB Output is correct
19 Correct 31 ms 96604 KB Output is correct
20 Correct 29 ms 95824 KB Output is correct
21 Correct 26 ms 92500 KB Output is correct
22 Correct 45 ms 104528 KB Output is correct
23 Correct 54 ms 104344 KB Output is correct
24 Correct 45 ms 104528 KB Output is correct
25 Correct 43 ms 104276 KB Output is correct
26 Correct 41 ms 104364 KB Output is correct
27 Correct 41 ms 104244 KB Output is correct
28 Correct 40 ms 104276 KB Output is correct
29 Correct 33 ms 101716 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 91732 KB Output is correct
2 Correct 32 ms 96552 KB Output is correct
3 Correct 30 ms 96500 KB Output is correct
4 Correct 30 ms 96464 KB Output is correct
5 Correct 31 ms 96480 KB Output is correct
6 Correct 29 ms 96604 KB Output is correct
7 Correct 25 ms 95568 KB Output is correct
8 Correct 30 ms 94084 KB Output is correct
9 Correct 38 ms 96688 KB Output is correct
10 Correct 28 ms 96548 KB Output is correct
11 Correct 37 ms 96592 KB Output is correct
12 Correct 27 ms 96592 KB Output is correct
13 Correct 26 ms 91552 KB Output is correct
14 Correct 23 ms 92508 KB Output is correct
15 Correct 25 ms 92888 KB Output is correct
16 Correct 27 ms 91740 KB Output is correct
17 Correct 45 ms 104528 KB Output is correct
18 Correct 54 ms 104344 KB Output is correct
19 Correct 45 ms 104528 KB Output is correct
20 Correct 43 ms 104276 KB Output is correct
21 Correct 41 ms 104364 KB Output is correct
22 Correct 41 ms 104244 KB Output is correct
23 Correct 40 ms 104276 KB Output is correct
24 Correct 33 ms 101716 KB Output is correct
25 Correct 22 ms 91484 KB Output is correct
26 Correct 26 ms 91844 KB Output is correct
27 Correct 31 ms 96604 KB Output is correct
28 Correct 29 ms 95824 KB Output is correct
29 Correct 26 ms 92500 KB Output is correct
30 Correct 92 ms 126948 KB Output is correct
31 Correct 99 ms 127116 KB Output is correct
32 Correct 91 ms 127052 KB Output is correct
33 Correct 82 ms 125780 KB Output is correct
34 Correct 101 ms 126548 KB Output is correct
35 Correct 92 ms 126544 KB Output is correct
36 Correct 102 ms 126188 KB Output is correct
37 Correct 85 ms 126868 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 91732 KB Output is correct
2 Correct 32 ms 96552 KB Output is correct
3 Correct 30 ms 96500 KB Output is correct
4 Correct 30 ms 96464 KB Output is correct
5 Correct 31 ms 96480 KB Output is correct
6 Correct 29 ms 96604 KB Output is correct
7 Correct 25 ms 95568 KB Output is correct
8 Correct 30 ms 94084 KB Output is correct
9 Correct 38 ms 96688 KB Output is correct
10 Correct 28 ms 96548 KB Output is correct
11 Correct 37 ms 96592 KB Output is correct
12 Correct 27 ms 96592 KB Output is correct
13 Correct 26 ms 91552 KB Output is correct
14 Correct 23 ms 92508 KB Output is correct
15 Correct 25 ms 92888 KB Output is correct
16 Correct 27 ms 91740 KB Output is correct
17 Correct 45 ms 104528 KB Output is correct
18 Correct 54 ms 104344 KB Output is correct
19 Correct 45 ms 104528 KB Output is correct
20 Correct 43 ms 104276 KB Output is correct
21 Correct 41 ms 104364 KB Output is correct
22 Correct 41 ms 104244 KB Output is correct
23 Correct 40 ms 104276 KB Output is correct
24 Correct 33 ms 101716 KB Output is correct
25 Correct 92 ms 126948 KB Output is correct
26 Correct 99 ms 127116 KB Output is correct
27 Correct 91 ms 127052 KB Output is correct
28 Correct 82 ms 125780 KB Output is correct
29 Correct 101 ms 126548 KB Output is correct
30 Correct 92 ms 126544 KB Output is correct
31 Correct 102 ms 126188 KB Output is correct
32 Correct 85 ms 126868 KB Output is correct
33 Correct 22 ms 91484 KB Output is correct
34 Correct 26 ms 91844 KB Output is correct
35 Correct 31 ms 96604 KB Output is correct
36 Correct 29 ms 95824 KB Output is correct
37 Correct 26 ms 92500 KB Output is correct
38 Correct 211 ms 229464 KB Output is correct
39 Correct 223 ms 229356 KB Output is correct
40 Correct 211 ms 229252 KB Output is correct
41 Correct 236 ms 229460 KB Output is correct
42 Correct 581 ms 261204 KB Output is correct
43 Correct 602 ms 262444 KB Output is correct
44 Correct 605 ms 261200 KB Output is correct
45 Correct 585 ms 253008 KB Output is correct
46 Correct 336 ms 240208 KB Output is correct
47 Correct 417 ms 244028 KB Output is correct
48 Correct 597 ms 255772 KB Output is correct
49 Correct 647 ms 254804 KB Output is correct
50 Correct 327 ms 204344 KB Output is correct
51 Correct 335 ms 194132 KB Output is correct
52 Correct 559 ms 249940 KB Output is correct
53 Correct 551 ms 250192 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 172884 KB Output is correct
2 Correct 323 ms 172848 KB Output is correct
3 Correct 308 ms 172628 KB Output is correct
4 Correct 22 ms 91480 KB Output is correct
5 Correct 305 ms 172780 KB Output is correct
6 Correct 349 ms 172628 KB Output is correct
7 Correct 320 ms 172628 KB Output is correct
8 Correct 333 ms 172628 KB Output is correct
9 Correct 325 ms 172628 KB Output is correct
10 Correct 331 ms 172640 KB Output is correct
11 Correct 337 ms 172572 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 91484 KB Output is correct
2 Correct 26 ms 91844 KB Output is correct
3 Correct 31 ms 96604 KB Output is correct
4 Correct 29 ms 95824 KB Output is correct
5 Correct 26 ms 92500 KB Output is correct
6 Correct 27 ms 92832 KB Output is correct
7 Correct 1815 ms 513812 KB Output is correct
8 Correct 3724 ms 867156 KB Output is correct
9 Correct 3476 ms 870744 KB Output is correct
10 Correct 3475 ms 870188 KB Output is correct
11 Correct 751 ms 456864 KB Output is correct
12 Correct 1112 ms 730448 KB Output is correct
13 Correct 1140 ms 736336 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 91732 KB Output is correct
2 Correct 32 ms 96552 KB Output is correct
3 Correct 30 ms 96500 KB Output is correct
4 Correct 30 ms 96464 KB Output is correct
5 Correct 31 ms 96480 KB Output is correct
6 Correct 29 ms 96604 KB Output is correct
7 Correct 25 ms 95568 KB Output is correct
8 Correct 30 ms 94084 KB Output is correct
9 Correct 38 ms 96688 KB Output is correct
10 Correct 28 ms 96548 KB Output is correct
11 Correct 37 ms 96592 KB Output is correct
12 Correct 27 ms 96592 KB Output is correct
13 Correct 26 ms 91552 KB Output is correct
14 Correct 23 ms 92508 KB Output is correct
15 Correct 25 ms 92888 KB Output is correct
16 Correct 27 ms 91740 KB Output is correct
17 Correct 45 ms 104528 KB Output is correct
18 Correct 54 ms 104344 KB Output is correct
19 Correct 45 ms 104528 KB Output is correct
20 Correct 43 ms 104276 KB Output is correct
21 Correct 41 ms 104364 KB Output is correct
22 Correct 41 ms 104244 KB Output is correct
23 Correct 40 ms 104276 KB Output is correct
24 Correct 33 ms 101716 KB Output is correct
25 Correct 92 ms 126948 KB Output is correct
26 Correct 99 ms 127116 KB Output is correct
27 Correct 91 ms 127052 KB Output is correct
28 Correct 82 ms 125780 KB Output is correct
29 Correct 101 ms 126548 KB Output is correct
30 Correct 92 ms 126544 KB Output is correct
31 Correct 102 ms 126188 KB Output is correct
32 Correct 85 ms 126868 KB Output is correct
33 Correct 211 ms 229464 KB Output is correct
34 Correct 223 ms 229356 KB Output is correct
35 Correct 211 ms 229252 KB Output is correct
36 Correct 236 ms 229460 KB Output is correct
37 Correct 581 ms 261204 KB Output is correct
38 Correct 602 ms 262444 KB Output is correct
39 Correct 605 ms 261200 KB Output is correct
40 Correct 585 ms 253008 KB Output is correct
41 Correct 336 ms 240208 KB Output is correct
42 Correct 417 ms 244028 KB Output is correct
43 Correct 597 ms 255772 KB Output is correct
44 Correct 647 ms 254804 KB Output is correct
45 Correct 327 ms 204344 KB Output is correct
46 Correct 335 ms 194132 KB Output is correct
47 Correct 559 ms 249940 KB Output is correct
48 Correct 551 ms 250192 KB Output is correct
49 Correct 366 ms 172884 KB Output is correct
50 Correct 323 ms 172848 KB Output is correct
51 Correct 308 ms 172628 KB Output is correct
52 Correct 22 ms 91480 KB Output is correct
53 Correct 305 ms 172780 KB Output is correct
54 Correct 349 ms 172628 KB Output is correct
55 Correct 320 ms 172628 KB Output is correct
56 Correct 333 ms 172628 KB Output is correct
57 Correct 325 ms 172628 KB Output is correct
58 Correct 331 ms 172640 KB Output is correct
59 Correct 337 ms 172572 KB Output is correct
60 Correct 27 ms 92832 KB Output is correct
61 Correct 1815 ms 513812 KB Output is correct
62 Correct 3724 ms 867156 KB Output is correct
63 Correct 3476 ms 870744 KB Output is correct
64 Correct 3475 ms 870188 KB Output is correct
65 Correct 751 ms 456864 KB Output is correct
66 Correct 1112 ms 730448 KB Output is correct
67 Correct 1140 ms 736336 KB Output is correct
68 Correct 22 ms 91484 KB Output is correct
69 Correct 26 ms 91844 KB Output is correct
70 Correct 31 ms 96604 KB Output is correct
71 Correct 29 ms 95824 KB Output is correct
72 Correct 26 ms 92500 KB Output is correct
73 Correct 1285 ms 722280 KB Output is correct
74 Correct 1208 ms 722384 KB Output is correct
75 Correct 1273 ms 722516 KB Output is correct
76 Correct 1256 ms 722256 KB Output is correct
77 Runtime error 2024 ms 1048576 KB Execution killed with signal 9
78 Halted 0 ms 0 KB -