oj.uz

Submission #928808

# Submission time Handle Problem Language Result Execution time Memory
928808 2024-02-17T06:04:44 Z knon0501 Rectangles (IOI19_rect) C++17
59 / 100
 1416 ms 1048576 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> b[2505][2505];
vector<int> c[2505][2505];
vector<pair<int,int>> d[2505][2505];
vector<pair<int,int>> e[2505][2505];

int lef[2505][2505];
int rig[2505][2505];
int up[2505][2505];
int down[2505][2505];
vector<vector<int>> v;

long long count_rectangles(std::vector<std::vector<int> > a) {



	int n = a.size();
	int m = a[0].size();


	
	
	
	for(int i=1 ; i<n-1 ; i++){
		stack<int> S;

		for(int j=0 ; j<m ; j++){
			bool flag = true;
			while(!S.empty() && a[i][S.top()] <=  a[i][j]){
				int x = S.top(); 
				
				
				if(x +1 <j && flag)
					b[x+1][j-1].push_back(i);
				if(a[i][S.top()]==a[i][j])flag=false;
				S.pop();
				
			}
			if(!S.empty() ){
				int x = S.top();
				lef[i][j] = x;
				if(x+1<j && flag)
					b[x+1][j-1].push_back(i);
			}
			else{
				lef[i][j]=-1;
			}
			S.push(j);
		}
		while(!S.empty())S.pop();
		for(int j=m-1; j>=0 ; j--){
		
			while(!S.empty() && a[i][S.top()] <=  a[i][j]){
				
				S.pop();
				
			}
			if(!S.empty() ){
				int x = S.top();
				rig[i][j] = x;
				
			}
			else{
				rig[i][j]=-1;
			}
			S.push(j);
		}
	}

	for(int i=1 ; i<m-1 ; i++){
		stack<int> S;

		for(int j=0 ; j<n ; j++){
			bool flag = true;
			while(!S.empty() && a[S.top()][i] <=  a[j][i]){
				int x = S.top(); 
				
				
				if(x +1 <j && flag)
					c[x+1][j-1].push_back(i);
				if(a[S.top()][i]==a[j][i])flag=false;
				S.pop();
				
			}
			
			if(!S.empty() ){
				
				int x = S.top();
		
				up[j][i]=x;
				if(x+1<j && flag)
					c[x+1][j-1].push_back(i);
			}
			else{
				up[j][i]=-1;
			}
			S.push(j);
		}
		while(!S.empty())S.pop();
		for(int j=n-1 ; j>=0 ; j--){
			while(!S.empty() && a[S.top()][i] <=  a[j][i]){
			
				S.pop();
				
			}
			if(!S.empty() ){
				int x = S.top();
				down[j][i]=x;	
			}
			else{
				down[j][i]=-1;
			}
			S.push(j);
		}
	}
	long long ans = 0;
	for(int i=1 ; i<m ; i++){
		for(int j=i ; j<m ; j++){
			reverse(b[i][j].begin(),b[i][j].end());
			int prv = -1;
			int y;
			for(auto x: b[i][j]){
				if(x != prv-1){
					if(prv>=0)
						d[i][j].push_back({prv,y});
					y=x;
				}
				prv=x;
			}
			if(prv>=0){

				d[i][j].push_back({prv,y});
			}
			sort(d[i][j].begin(),d[i][j].end());
			b[i][j].clear();
		}
	}
	for(int i=1 ; i<n  ; i++){
		for(int j=i ; j<n ; j++){
			reverse(c[i][j].begin(),c[i][j].end());
			int prv = -1;
			int y;
			for(auto x: c[i][j]){
				if(x != prv-1){
					if(prv>=0)
						e[i][j].push_back({prv,y});
					y=x;
				}
				prv=x;
			}
			if(prv>=0){
			
				e[i][j].push_back({prv,y});
			}
			sort(e[i][j].begin(),e[i][j].end());
			c[i][j].clear();
		}
	}
	
	for(int i = 1 ; i<n-1 ; i++){
		for(int j=1 ; j<m-1 ; j++){
			int x = lef[i][j];
			int y = rig[i][j];
			int z = up[i][j];
			int w = down[i][j];
			v.push_back({x,y,z,w});
			
		}
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(auto vv: v){
		int x=vv[0];
		int y = vv[1];
		int z =vv[2];
		int  w = vv[3];
		if(x==-1 ||y==-1 || z==-1 || w==-1)continue;
			
			auto k = upper_bound(d[x+1][y-1].begin(),d[x+1][y-1].end(),make_pair(z+1,10000000));
			if(k== d[x+1][y-1].begin())continue;
		
			if((--k)->second <w-1)continue;
			
			//cout<<z+1<<" "<<w-1<<" "<<e[z+1][w-1].size()<<" "<<c[z+1][w-1].size()<<endl;
			auto t = upper_bound(e[z+1][w-1].begin(),e[z+1][w-1].end(),make_pair(x+1,10000000));
			
			if(t== e[z+1][w-1].begin())continue;
			
			if((--t)->second <y-1)continue;
			ans++;
	}
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 591444 KB Output is correct
2 Correct 141 ms 591836 KB Output is correct
3 Correct 140 ms 591992 KB Output is correct
4 Correct 141 ms 591824 KB Output is correct
5 Correct 139 ms 591820 KB Output is correct
6 Correct 143 ms 591956 KB Output is correct
7 Correct 140 ms 591852 KB Output is correct
8 Correct 139 ms 591700 KB Output is correct
9 Correct 143 ms 591876 KB Output is correct
10 Correct 141 ms 591956 KB Output is correct
11 Correct 142 ms 591956 KB Output is correct
12 Correct 143 ms 592048 KB Output is correct
13 Correct 142 ms 591476 KB Output is correct
14 Correct 135 ms 591444 KB Output is correct
15 Correct 133 ms 597488 KB Output is correct
16 Correct 136 ms 597588 KB Output is correct
17 Correct 136 ms 591404 KB Output is correct
18 Correct 133 ms 593336 KB Output is correct
19 Correct 134 ms 601660 KB Output is correct
20 Correct 135 ms 601684 KB Output is correct
21 Correct 133 ms 595372 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 591444 KB Output is correct
2 Correct 141 ms 591836 KB Output is correct
3 Correct 140 ms 591992 KB Output is correct
4 Correct 141 ms 591824 KB Output is correct
5 Correct 139 ms 591820 KB Output is correct
6 Correct 143 ms 591956 KB Output is correct
7 Correct 140 ms 591852 KB Output is correct
8 Correct 139 ms 591700 KB Output is correct
9 Correct 143 ms 591876 KB Output is correct
10 Correct 141 ms 591956 KB Output is correct
11 Correct 142 ms 591956 KB Output is correct
12 Correct 143 ms 592048 KB Output is correct
13 Correct 142 ms 591476 KB Output is correct
14 Correct 135 ms 591444 KB Output is correct
15 Correct 133 ms 597488 KB Output is correct
16 Correct 136 ms 597588 KB Output is correct
17 Correct 136 ms 591404 KB Output is correct
18 Correct 133 ms 593336 KB Output is correct
19 Correct 134 ms 601660 KB Output is correct
20 Correct 135 ms 601684 KB Output is correct
21 Correct 133 ms 595372 KB Output is correct
22 Correct 141 ms 606292 KB Output is correct
23 Correct 140 ms 606288 KB Output is correct
24 Correct 137 ms 606324 KB Output is correct
25 Correct 134 ms 606284 KB Output is correct
26 Correct 144 ms 606416 KB Output is correct
27 Correct 136 ms 606380 KB Output is correct
28 Correct 139 ms 606876 KB Output is correct
29 Correct 137 ms 605988 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 591444 KB Output is correct
2 Correct 141 ms 591836 KB Output is correct
3 Correct 140 ms 591992 KB Output is correct
4 Correct 141 ms 591824 KB Output is correct
5 Correct 139 ms 591820 KB Output is correct
6 Correct 143 ms 591956 KB Output is correct
7 Correct 140 ms 591852 KB Output is correct
8 Correct 139 ms 591700 KB Output is correct
9 Correct 143 ms 591876 KB Output is correct
10 Correct 141 ms 591956 KB Output is correct
11 Correct 142 ms 591956 KB Output is correct
12 Correct 143 ms 592048 KB Output is correct
13 Correct 142 ms 591476 KB Output is correct
14 Correct 135 ms 591444 KB Output is correct
15 Correct 133 ms 597488 KB Output is correct
16 Correct 136 ms 597588 KB Output is correct
17 Correct 141 ms 606292 KB Output is correct
18 Correct 140 ms 606288 KB Output is correct
19 Correct 137 ms 606324 KB Output is correct
20 Correct 134 ms 606284 KB Output is correct
21 Correct 144 ms 606416 KB Output is correct
22 Correct 136 ms 606380 KB Output is correct
23 Correct 139 ms 606876 KB Output is correct
24 Correct 137 ms 605988 KB Output is correct
25 Correct 136 ms 591404 KB Output is correct
26 Correct 133 ms 593336 KB Output is correct
27 Correct 134 ms 601660 KB Output is correct
28 Correct 135 ms 601684 KB Output is correct
29 Correct 133 ms 595372 KB Output is correct
30 Correct 148 ms 609292 KB Output is correct
31 Correct 149 ms 609316 KB Output is correct
32 Correct 149 ms 609544 KB Output is correct
33 Correct 145 ms 609288 KB Output is correct
34 Correct 154 ms 610316 KB Output is correct
35 Correct 151 ms 610528 KB Output is correct
36 Correct 149 ms 610164 KB Output is correct
37 Correct 149 ms 610060 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 591444 KB Output is correct
2 Correct 141 ms 591836 KB Output is correct
3 Correct 140 ms 591992 KB Output is correct
4 Correct 141 ms 591824 KB Output is correct
5 Correct 139 ms 591820 KB Output is correct
6 Correct 143 ms 591956 KB Output is correct
7 Correct 140 ms 591852 KB Output is correct
8 Correct 139 ms 591700 KB Output is correct
9 Correct 143 ms 591876 KB Output is correct
10 Correct 141 ms 591956 KB Output is correct
11 Correct 142 ms 591956 KB Output is correct
12 Correct 143 ms 592048 KB Output is correct
13 Correct 142 ms 591476 KB Output is correct
14 Correct 135 ms 591444 KB Output is correct
15 Correct 133 ms 597488 KB Output is correct
16 Correct 136 ms 597588 KB Output is correct
17 Correct 141 ms 606292 KB Output is correct
18 Correct 140 ms 606288 KB Output is correct
19 Correct 137 ms 606324 KB Output is correct
20 Correct 134 ms 606284 KB Output is correct
21 Correct 144 ms 606416 KB Output is correct
22 Correct 136 ms 606380 KB Output is correct
23 Correct 139 ms 606876 KB Output is correct
24 Correct 137 ms 605988 KB Output is correct
25 Correct 148 ms 609292 KB Output is correct
26 Correct 149 ms 609316 KB Output is correct
27 Correct 149 ms 609544 KB Output is correct
28 Correct 145 ms 609288 KB Output is correct
29 Correct 154 ms 610316 KB Output is correct
30 Correct 151 ms 610528 KB Output is correct
31 Correct 149 ms 610164 KB Output is correct
32 Correct 149 ms 610060 KB Output is correct
33 Correct 136 ms 591404 KB Output is correct
34 Correct 133 ms 593336 KB Output is correct
35 Correct 134 ms 601660 KB Output is correct
36 Correct 135 ms 601684 KB Output is correct
37 Correct 133 ms 595372 KB Output is correct
38 Correct 343 ms 694712 KB Output is correct
39 Correct 317 ms 694852 KB Output is correct
40 Correct 316 ms 694832 KB Output is correct
41 Correct 292 ms 695548 KB Output is correct
42 Correct 297 ms 670204 KB Output is correct
43 Correct 310 ms 669936 KB Output is correct
44 Correct 301 ms 670564 KB Output is correct
45 Correct 301 ms 665636 KB Output is correct
46 Correct 301 ms 666360 KB Output is correct
47 Correct 341 ms 668180 KB Output is correct
48 Correct 396 ms 680416 KB Output is correct
49 Correct 405 ms 681876 KB Output is correct
50 Correct 264 ms 656228 KB Output is correct
51 Correct 257 ms 639744 KB Output is correct
52 Correct 386 ms 676856 KB Output is correct
53 Correct 396 ms 677880 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 598100 KB Output is correct
2 Correct 139 ms 597840 KB Output is correct
3 Correct 144 ms 597736 KB Output is correct
4 Correct 133 ms 595576 KB Output is correct
5 Correct 141 ms 597968 KB Output is correct
6 Correct 145 ms 598056 KB Output is correct
7 Correct 146 ms 597884 KB Output is correct
8 Correct 145 ms 597840 KB Output is correct
9 Correct 143 ms 597904 KB Output is correct
10 Correct 140 ms 593536 KB Output is correct
11 Correct 143 ms 593632 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 591404 KB Output is correct
2 Correct 133 ms 593336 KB Output is correct
3 Correct 134 ms 601660 KB Output is correct
4 Correct 135 ms 601684 KB Output is correct
5 Correct 133 ms 595372 KB Output is correct
6 Correct 129 ms 597584 KB Output is correct
7 Correct 1416 ms 867176 KB Output is correct
8 Runtime error 845 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 591444 KB Output is correct
2 Correct 141 ms 591836 KB Output is correct
3 Correct 140 ms 591992 KB Output is correct
4 Correct 141 ms 591824 KB Output is correct
5 Correct 139 ms 591820 KB Output is correct
6 Correct 143 ms 591956 KB Output is correct
7 Correct 140 ms 591852 KB Output is correct
8 Correct 139 ms 591700 KB Output is correct
9 Correct 143 ms 591876 KB Output is correct
10 Correct 141 ms 591956 KB Output is correct
11 Correct 142 ms 591956 KB Output is correct
12 Correct 143 ms 592048 KB Output is correct
13 Correct 142 ms 591476 KB Output is correct
14 Correct 135 ms 591444 KB Output is correct
15 Correct 133 ms 597488 KB Output is correct
16 Correct 136 ms 597588 KB Output is correct
17 Correct 141 ms 606292 KB Output is correct
18 Correct 140 ms 606288 KB Output is correct
19 Correct 137 ms 606324 KB Output is correct
20 Correct 134 ms 606284 KB Output is correct
21 Correct 144 ms 606416 KB Output is correct
22 Correct 136 ms 606380 KB Output is correct
23 Correct 139 ms 606876 KB Output is correct
24 Correct 137 ms 605988 KB Output is correct
25 Correct 148 ms 609292 KB Output is correct
26 Correct 149 ms 609316 KB Output is correct
27 Correct 149 ms 609544 KB Output is correct
28 Correct 145 ms 609288 KB Output is correct
29 Correct 154 ms 610316 KB Output is correct
30 Correct 151 ms 610528 KB Output is correct
31 Correct 149 ms 610164 KB Output is correct
32 Correct 149 ms 610060 KB Output is correct
33 Correct 343 ms 694712 KB Output is correct
34 Correct 317 ms 694852 KB Output is correct
35 Correct 316 ms 694832 KB Output is correct
36 Correct 292 ms 695548 KB Output is correct
37 Correct 297 ms 670204 KB Output is correct
38 Correct 310 ms 669936 KB Output is correct
39 Correct 301 ms 670564 KB Output is correct
40 Correct 301 ms 665636 KB Output is correct
41 Correct 301 ms 666360 KB Output is correct
42 Correct 341 ms 668180 KB Output is correct
43 Correct 396 ms 680416 KB Output is correct
44 Correct 405 ms 681876 KB Output is correct
45 Correct 264 ms 656228 KB Output is correct
46 Correct 257 ms 639744 KB Output is correct
47 Correct 386 ms 676856 KB Output is correct
48 Correct 396 ms 677880 KB Output is correct
49 Correct 144 ms 598100 KB Output is correct
50 Correct 139 ms 597840 KB Output is correct
51 Correct 144 ms 597736 KB Output is correct
52 Correct 133 ms 595576 KB Output is correct
53 Correct 141 ms 597968 KB Output is correct
54 Correct 145 ms 598056 KB Output is correct
55 Correct 146 ms 597884 KB Output is correct
56 Correct 145 ms 597840 KB Output is correct
57 Correct 143 ms 597904 KB Output is correct
58 Correct 140 ms 593536 KB Output is correct
59 Correct 143 ms 593632 KB Output is correct
60 Correct 129 ms 597584 KB Output is correct
61 Correct 1416 ms 867176 KB Output is correct
62 Runtime error 845 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -