oj.uz

Submission #928799

# Submission time Handle Problem Language Result Execution time Memory
928799 2024-02-17T05:59:25 Z knon0501 Rectangles (IOI19_rect) C++14
59 / 100
 1592 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];

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());
		}
	}
	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());
		}
	}
	vector<vector<int>> v;
	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 278 ms 589768 KB Output is correct
2 Correct 237 ms 590160 KB Output is correct
3 Correct 239 ms 590220 KB Output is correct
4 Correct 260 ms 590172 KB Output is correct
5 Correct 237 ms 590164 KB Output is correct
6 Correct 237 ms 590212 KB Output is correct
7 Correct 238 ms 590160 KB Output is correct
8 Correct 240 ms 589904 KB Output is correct
9 Correct 236 ms 590416 KB Output is correct
10 Correct 236 ms 590416 KB Output is correct
11 Correct 246 ms 590332 KB Output is correct
12 Correct 239 ms 590420 KB Output is correct
13 Correct 241 ms 589648 KB Output is correct
14 Correct 235 ms 589756 KB Output is correct
15 Correct 237 ms 589908 KB Output is correct
16 Correct 244 ms 590044 KB Output is correct
17 Correct 238 ms 589648 KB Output is correct
18 Correct 237 ms 589648 KB Output is correct
19 Correct 238 ms 590416 KB Output is correct
20 Correct 237 ms 590160 KB Output is correct
21 Correct 240 ms 589996 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 589768 KB Output is correct
2 Correct 237 ms 590160 KB Output is correct
3 Correct 239 ms 590220 KB Output is correct
4 Correct 260 ms 590172 KB Output is correct
5 Correct 237 ms 590164 KB Output is correct
6 Correct 237 ms 590212 KB Output is correct
7 Correct 238 ms 590160 KB Output is correct
8 Correct 240 ms 589904 KB Output is correct
9 Correct 236 ms 590416 KB Output is correct
10 Correct 236 ms 590416 KB Output is correct
11 Correct 246 ms 590332 KB Output is correct
12 Correct 239 ms 590420 KB Output is correct
13 Correct 241 ms 589648 KB Output is correct
14 Correct 235 ms 589756 KB Output is correct
15 Correct 237 ms 589908 KB Output is correct
16 Correct 244 ms 590044 KB Output is correct
17 Correct 238 ms 589648 KB Output is correct
18 Correct 237 ms 589648 KB Output is correct
19 Correct 238 ms 590416 KB Output is correct
20 Correct 237 ms 590160 KB Output is correct
21 Correct 240 ms 589996 KB Output is correct
22 Correct 241 ms 591768 KB Output is correct
23 Correct 245 ms 591720 KB Output is correct
24 Correct 244 ms 591672 KB Output is correct
25 Correct 239 ms 591700 KB Output is correct
26 Correct 242 ms 591740 KB Output is correct
27 Correct 238 ms 591700 KB Output is correct
28 Correct 240 ms 591652 KB Output is correct
29 Correct 246 ms 591472 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 589768 KB Output is correct
2 Correct 237 ms 590160 KB Output is correct
3 Correct 239 ms 590220 KB Output is correct
4 Correct 260 ms 590172 KB Output is correct
5 Correct 237 ms 590164 KB Output is correct
6 Correct 237 ms 590212 KB Output is correct
7 Correct 238 ms 590160 KB Output is correct
8 Correct 240 ms 589904 KB Output is correct
9 Correct 236 ms 590416 KB Output is correct
10 Correct 236 ms 590416 KB Output is correct
11 Correct 246 ms 590332 KB Output is correct
12 Correct 239 ms 590420 KB Output is correct
13 Correct 241 ms 589648 KB Output is correct
14 Correct 235 ms 589756 KB Output is correct
15 Correct 237 ms 589908 KB Output is correct
16 Correct 244 ms 590044 KB Output is correct
17 Correct 241 ms 591768 KB Output is correct
18 Correct 245 ms 591720 KB Output is correct
19 Correct 244 ms 591672 KB Output is correct
20 Correct 239 ms 591700 KB Output is correct
21 Correct 242 ms 591740 KB Output is correct
22 Correct 238 ms 591700 KB Output is correct
23 Correct 240 ms 591652 KB Output is correct
24 Correct 246 ms 591472 KB Output is correct
25 Correct 238 ms 589648 KB Output is correct
26 Correct 237 ms 589648 KB Output is correct
27 Correct 238 ms 590416 KB Output is correct
28 Correct 237 ms 590160 KB Output is correct
29 Correct 240 ms 589996 KB Output is correct
30 Correct 248 ms 597084 KB Output is correct
31 Correct 252 ms 597000 KB Output is correct
32 Correct 257 ms 597236 KB Output is correct
33 Correct 255 ms 597020 KB Output is correct
34 Correct 257 ms 598112 KB Output is correct
35 Correct 260 ms 598284 KB Output is correct
36 Correct 258 ms 597772 KB Output is correct
37 Correct 261 ms 597944 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 589768 KB Output is correct
2 Correct 237 ms 590160 KB Output is correct
3 Correct 239 ms 590220 KB Output is correct
4 Correct 260 ms 590172 KB Output is correct
5 Correct 237 ms 590164 KB Output is correct
6 Correct 237 ms 590212 KB Output is correct
7 Correct 238 ms 590160 KB Output is correct
8 Correct 240 ms 589904 KB Output is correct
9 Correct 236 ms 590416 KB Output is correct
10 Correct 236 ms 590416 KB Output is correct
11 Correct 246 ms 590332 KB Output is correct
12 Correct 239 ms 590420 KB Output is correct
13 Correct 241 ms 589648 KB Output is correct
14 Correct 235 ms 589756 KB Output is correct
15 Correct 237 ms 589908 KB Output is correct
16 Correct 244 ms 590044 KB Output is correct
17 Correct 241 ms 591768 KB Output is correct
18 Correct 245 ms 591720 KB Output is correct
19 Correct 244 ms 591672 KB Output is correct
20 Correct 239 ms 591700 KB Output is correct
21 Correct 242 ms 591740 KB Output is correct
22 Correct 238 ms 591700 KB Output is correct
23 Correct 240 ms 591652 KB Output is correct
24 Correct 246 ms 591472 KB Output is correct
25 Correct 248 ms 597084 KB Output is correct
26 Correct 252 ms 597000 KB Output is correct
27 Correct 257 ms 597236 KB Output is correct
28 Correct 255 ms 597020 KB Output is correct
29 Correct 257 ms 598112 KB Output is correct
30 Correct 260 ms 598284 KB Output is correct
31 Correct 258 ms 597772 KB Output is correct
32 Correct 261 ms 597944 KB Output is correct
33 Correct 238 ms 589648 KB Output is correct
34 Correct 237 ms 589648 KB Output is correct
35 Correct 238 ms 590416 KB Output is correct
36 Correct 237 ms 590160 KB Output is correct
37 Correct 240 ms 589996 KB Output is correct
38 Correct 445 ms 673044 KB Output is correct
39 Correct 424 ms 672816 KB Output is correct
40 Correct 440 ms 672972 KB Output is correct
41 Correct 413 ms 673016 KB Output is correct
42 Correct 418 ms 648184 KB Output is correct
43 Correct 424 ms 648188 KB Output is correct
44 Correct 414 ms 648808 KB Output is correct
45 Correct 411 ms 644868 KB Output is correct
46 Correct 417 ms 644604 KB Output is correct
47 Correct 446 ms 646136 KB Output is correct
48 Correct 506 ms 657664 KB Output is correct
49 Correct 514 ms 659968 KB Output is correct
50 Correct 377 ms 630528 KB Output is correct
51 Correct 364 ms 624920 KB Output is correct
52 Correct 495 ms 654844 KB Output is correct
53 Correct 487 ms 655864 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 590160 KB Output is correct
2 Correct 254 ms 590272 KB Output is correct
3 Correct 247 ms 590160 KB Output is correct
4 Correct 237 ms 589652 KB Output is correct
5 Correct 248 ms 590388 KB Output is correct
6 Correct 253 ms 590160 KB Output is correct
7 Correct 250 ms 590300 KB Output is correct
8 Correct 250 ms 590164 KB Output is correct
9 Correct 256 ms 590308 KB Output is correct
10 Correct 250 ms 589904 KB Output is correct
11 Correct 249 ms 589908 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 589648 KB Output is correct
2 Correct 237 ms 589648 KB Output is correct
3 Correct 238 ms 590416 KB Output is correct
4 Correct 237 ms 590160 KB Output is correct
5 Correct 240 ms 589996 KB Output is correct
6 Correct 237 ms 589900 KB Output is correct
7 Correct 1592 ms 851096 KB Output is correct
8 Runtime error 1036 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 278 ms 589768 KB Output is correct
2 Correct 237 ms 590160 KB Output is correct
3 Correct 239 ms 590220 KB Output is correct
4 Correct 260 ms 590172 KB Output is correct
5 Correct 237 ms 590164 KB Output is correct
6 Correct 237 ms 590212 KB Output is correct
7 Correct 238 ms 590160 KB Output is correct
8 Correct 240 ms 589904 KB Output is correct
9 Correct 236 ms 590416 KB Output is correct
10 Correct 236 ms 590416 KB Output is correct
11 Correct 246 ms 590332 KB Output is correct
12 Correct 239 ms 590420 KB Output is correct
13 Correct 241 ms 589648 KB Output is correct
14 Correct 235 ms 589756 KB Output is correct
15 Correct 237 ms 589908 KB Output is correct
16 Correct 244 ms 590044 KB Output is correct
17 Correct 241 ms 591768 KB Output is correct
18 Correct 245 ms 591720 KB Output is correct
19 Correct 244 ms 591672 KB Output is correct
20 Correct 239 ms 591700 KB Output is correct
21 Correct 242 ms 591740 KB Output is correct
22 Correct 238 ms 591700 KB Output is correct
23 Correct 240 ms 591652 KB Output is correct
24 Correct 246 ms 591472 KB Output is correct
25 Correct 248 ms 597084 KB Output is correct
26 Correct 252 ms 597000 KB Output is correct
27 Correct 257 ms 597236 KB Output is correct
28 Correct 255 ms 597020 KB Output is correct
29 Correct 257 ms 598112 KB Output is correct
30 Correct 260 ms 598284 KB Output is correct
31 Correct 258 ms 597772 KB Output is correct
32 Correct 261 ms 597944 KB Output is correct
33 Correct 445 ms 673044 KB Output is correct
34 Correct 424 ms 672816 KB Output is correct
35 Correct 440 ms 672972 KB Output is correct
36 Correct 413 ms 673016 KB Output is correct
37 Correct 418 ms 648184 KB Output is correct
38 Correct 424 ms 648188 KB Output is correct
39 Correct 414 ms 648808 KB Output is correct
40 Correct 411 ms 644868 KB Output is correct
41 Correct 417 ms 644604 KB Output is correct
42 Correct 446 ms 646136 KB Output is correct
43 Correct 506 ms 657664 KB Output is correct
44 Correct 514 ms 659968 KB Output is correct
45 Correct 377 ms 630528 KB Output is correct
46 Correct 364 ms 624920 KB Output is correct
47 Correct 495 ms 654844 KB Output is correct
48 Correct 487 ms 655864 KB Output is correct
49 Correct 254 ms 590160 KB Output is correct
50 Correct 254 ms 590272 KB Output is correct
51 Correct 247 ms 590160 KB Output is correct
52 Correct 237 ms 589652 KB Output is correct
53 Correct 248 ms 590388 KB Output is correct
54 Correct 253 ms 590160 KB Output is correct
55 Correct 250 ms 590300 KB Output is correct
56 Correct 250 ms 590164 KB Output is correct
57 Correct 256 ms 590308 KB Output is correct
58 Correct 250 ms 589904 KB Output is correct
59 Correct 249 ms 589908 KB Output is correct
60 Correct 237 ms 589900 KB Output is correct
61 Correct 1592 ms 851096 KB Output is correct
62 Runtime error 1036 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -