oj.uz

Submission #928801

# Submission time Handle Problem Language Result Execution time Memory
928801 2024-02-17T06:01:37 Z knon0501 Rectangles (IOI19_rect) C++17
59 / 100
 1559 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());
		}
	}
	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());
		}
	}
	
	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 279 ms 589904 KB Output is correct
2 Correct 280 ms 590196 KB Output is correct
3 Correct 266 ms 590228 KB Output is correct
4 Correct 252 ms 590412 KB Output is correct
5 Correct 242 ms 590276 KB Output is correct
6 Correct 239 ms 590424 KB Output is correct
7 Correct 252 ms 590672 KB Output is correct
8 Correct 244 ms 590040 KB Output is correct
9 Correct 238 ms 590412 KB Output is correct
10 Correct 236 ms 590252 KB Output is correct
11 Correct 241 ms 590416 KB Output is correct
12 Correct 244 ms 590240 KB Output is correct
13 Correct 239 ms 589668 KB Output is correct
14 Correct 248 ms 589804 KB Output is correct
15 Correct 245 ms 589820 KB Output is correct
16 Correct 262 ms 589712 KB Output is correct
17 Correct 259 ms 589852 KB Output is correct
18 Correct 244 ms 589772 KB Output is correct
19 Correct 245 ms 590252 KB Output is correct
20 Correct 242 ms 590344 KB Output is correct
21 Correct 243 ms 589912 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 589904 KB Output is correct
2 Correct 280 ms 590196 KB Output is correct
3 Correct 266 ms 590228 KB Output is correct
4 Correct 252 ms 590412 KB Output is correct
5 Correct 242 ms 590276 KB Output is correct
6 Correct 239 ms 590424 KB Output is correct
7 Correct 252 ms 590672 KB Output is correct
8 Correct 244 ms 590040 KB Output is correct
9 Correct 238 ms 590412 KB Output is correct
10 Correct 236 ms 590252 KB Output is correct
11 Correct 241 ms 590416 KB Output is correct
12 Correct 244 ms 590240 KB Output is correct
13 Correct 239 ms 589668 KB Output is correct
14 Correct 248 ms 589804 KB Output is correct
15 Correct 245 ms 589820 KB Output is correct
16 Correct 262 ms 589712 KB Output is correct
17 Correct 259 ms 589852 KB Output is correct
18 Correct 244 ms 589772 KB Output is correct
19 Correct 245 ms 590252 KB Output is correct
20 Correct 242 ms 590344 KB Output is correct
21 Correct 243 ms 589912 KB Output is correct
22 Correct 253 ms 591568 KB Output is correct
23 Correct 245 ms 591656 KB Output is correct
24 Correct 245 ms 591568 KB Output is correct
25 Correct 241 ms 591624 KB Output is correct
26 Correct 241 ms 591900 KB Output is correct
27 Correct 258 ms 591752 KB Output is correct
28 Correct 258 ms 591784 KB Output is correct
29 Correct 243 ms 591444 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 589904 KB Output is correct
2 Correct 280 ms 590196 KB Output is correct
3 Correct 266 ms 590228 KB Output is correct
4 Correct 252 ms 590412 KB Output is correct
5 Correct 242 ms 590276 KB Output is correct
6 Correct 239 ms 590424 KB Output is correct
7 Correct 252 ms 590672 KB Output is correct
8 Correct 244 ms 590040 KB Output is correct
9 Correct 238 ms 590412 KB Output is correct
10 Correct 236 ms 590252 KB Output is correct
11 Correct 241 ms 590416 KB Output is correct
12 Correct 244 ms 590240 KB Output is correct
13 Correct 239 ms 589668 KB Output is correct
14 Correct 248 ms 589804 KB Output is correct
15 Correct 245 ms 589820 KB Output is correct
16 Correct 262 ms 589712 KB Output is correct
17 Correct 253 ms 591568 KB Output is correct
18 Correct 245 ms 591656 KB Output is correct
19 Correct 245 ms 591568 KB Output is correct
20 Correct 241 ms 591624 KB Output is correct
21 Correct 241 ms 591900 KB Output is correct
22 Correct 258 ms 591752 KB Output is correct
23 Correct 258 ms 591784 KB Output is correct
24 Correct 243 ms 591444 KB Output is correct
25 Correct 259 ms 589852 KB Output is correct
26 Correct 244 ms 589772 KB Output is correct
27 Correct 245 ms 590252 KB Output is correct
28 Correct 242 ms 590344 KB Output is correct
29 Correct 243 ms 589912 KB Output is correct
30 Correct 260 ms 597188 KB Output is correct
31 Correct 252 ms 597000 KB Output is correct
32 Correct 259 ms 597256 KB Output is correct
33 Correct 253 ms 597000 KB Output is correct
34 Correct 262 ms 598024 KB Output is correct
35 Correct 271 ms 598244 KB Output is correct
36 Correct 258 ms 597884 KB Output is correct
37 Correct 260 ms 597984 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 589904 KB Output is correct
2 Correct 280 ms 590196 KB Output is correct
3 Correct 266 ms 590228 KB Output is correct
4 Correct 252 ms 590412 KB Output is correct
5 Correct 242 ms 590276 KB Output is correct
6 Correct 239 ms 590424 KB Output is correct
7 Correct 252 ms 590672 KB Output is correct
8 Correct 244 ms 590040 KB Output is correct
9 Correct 238 ms 590412 KB Output is correct
10 Correct 236 ms 590252 KB Output is correct
11 Correct 241 ms 590416 KB Output is correct
12 Correct 244 ms 590240 KB Output is correct
13 Correct 239 ms 589668 KB Output is correct
14 Correct 248 ms 589804 KB Output is correct
15 Correct 245 ms 589820 KB Output is correct
16 Correct 262 ms 589712 KB Output is correct
17 Correct 253 ms 591568 KB Output is correct
18 Correct 245 ms 591656 KB Output is correct
19 Correct 245 ms 591568 KB Output is correct
20 Correct 241 ms 591624 KB Output is correct
21 Correct 241 ms 591900 KB Output is correct
22 Correct 258 ms 591752 KB Output is correct
23 Correct 258 ms 591784 KB Output is correct
24 Correct 243 ms 591444 KB Output is correct
25 Correct 260 ms 597188 KB Output is correct
26 Correct 252 ms 597000 KB Output is correct
27 Correct 259 ms 597256 KB Output is correct
28 Correct 253 ms 597000 KB Output is correct
29 Correct 262 ms 598024 KB Output is correct
30 Correct 271 ms 598244 KB Output is correct
31 Correct 258 ms 597884 KB Output is correct
32 Correct 260 ms 597984 KB Output is correct
33 Correct 259 ms 589852 KB Output is correct
34 Correct 244 ms 589772 KB Output is correct
35 Correct 245 ms 590252 KB Output is correct
36 Correct 242 ms 590344 KB Output is correct
37 Correct 243 ms 589912 KB Output is correct
38 Correct 448 ms 671480 KB Output is correct
39 Correct 428 ms 671732 KB Output is correct
40 Correct 432 ms 671692 KB Output is correct
41 Correct 409 ms 671532 KB Output is correct
42 Correct 448 ms 646636 KB Output is correct
43 Correct 424 ms 646652 KB Output is correct
44 Correct 434 ms 647232 KB Output is correct
45 Correct 424 ms 643576 KB Output is correct
46 Correct 422 ms 644340 KB Output is correct
47 Correct 455 ms 646268 KB Output is correct
48 Correct 524 ms 656892 KB Output is correct
49 Correct 531 ms 658248 KB Output is correct
50 Correct 391 ms 630260 KB Output is correct
51 Correct 370 ms 624380 KB Output is correct
52 Correct 501 ms 653628 KB Output is correct
53 Correct 500 ms 654332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 590420 KB Output is correct
2 Correct 256 ms 590164 KB Output is correct
3 Correct 257 ms 590228 KB Output is correct
4 Correct 243 ms 589652 KB Output is correct
5 Correct 257 ms 590416 KB Output is correct
6 Correct 273 ms 590232 KB Output is correct
7 Correct 258 ms 590328 KB Output is correct
8 Correct 251 ms 590240 KB Output is correct
9 Correct 275 ms 590216 KB Output is correct
10 Correct 255 ms 590164 KB Output is correct
11 Correct 249 ms 589904 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 589852 KB Output is correct
2 Correct 244 ms 589772 KB Output is correct
3 Correct 245 ms 590252 KB Output is correct
4 Correct 242 ms 590344 KB Output is correct
5 Correct 243 ms 589912 KB Output is correct
6 Correct 242 ms 589908 KB Output is correct
7 Correct 1559 ms 854240 KB Output is correct
8 Runtime error 1038 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 279 ms 589904 KB Output is correct
2 Correct 280 ms 590196 KB Output is correct
3 Correct 266 ms 590228 KB Output is correct
4 Correct 252 ms 590412 KB Output is correct
5 Correct 242 ms 590276 KB Output is correct
6 Correct 239 ms 590424 KB Output is correct
7 Correct 252 ms 590672 KB Output is correct
8 Correct 244 ms 590040 KB Output is correct
9 Correct 238 ms 590412 KB Output is correct
10 Correct 236 ms 590252 KB Output is correct
11 Correct 241 ms 590416 KB Output is correct
12 Correct 244 ms 590240 KB Output is correct
13 Correct 239 ms 589668 KB Output is correct
14 Correct 248 ms 589804 KB Output is correct
15 Correct 245 ms 589820 KB Output is correct
16 Correct 262 ms 589712 KB Output is correct
17 Correct 253 ms 591568 KB Output is correct
18 Correct 245 ms 591656 KB Output is correct
19 Correct 245 ms 591568 KB Output is correct
20 Correct 241 ms 591624 KB Output is correct
21 Correct 241 ms 591900 KB Output is correct
22 Correct 258 ms 591752 KB Output is correct
23 Correct 258 ms 591784 KB Output is correct
24 Correct 243 ms 591444 KB Output is correct
25 Correct 260 ms 597188 KB Output is correct
26 Correct 252 ms 597000 KB Output is correct
27 Correct 259 ms 597256 KB Output is correct
28 Correct 253 ms 597000 KB Output is correct
29 Correct 262 ms 598024 KB Output is correct
30 Correct 271 ms 598244 KB Output is correct
31 Correct 258 ms 597884 KB Output is correct
32 Correct 260 ms 597984 KB Output is correct
33 Correct 448 ms 671480 KB Output is correct
34 Correct 428 ms 671732 KB Output is correct
35 Correct 432 ms 671692 KB Output is correct
36 Correct 409 ms 671532 KB Output is correct
37 Correct 448 ms 646636 KB Output is correct
38 Correct 424 ms 646652 KB Output is correct
39 Correct 434 ms 647232 KB Output is correct
40 Correct 424 ms 643576 KB Output is correct
41 Correct 422 ms 644340 KB Output is correct
42 Correct 455 ms 646268 KB Output is correct
43 Correct 524 ms 656892 KB Output is correct
44 Correct 531 ms 658248 KB Output is correct
45 Correct 391 ms 630260 KB Output is correct
46 Correct 370 ms 624380 KB Output is correct
47 Correct 501 ms 653628 KB Output is correct
48 Correct 500 ms 654332 KB Output is correct
49 Correct 262 ms 590420 KB Output is correct
50 Correct 256 ms 590164 KB Output is correct
51 Correct 257 ms 590228 KB Output is correct
52 Correct 243 ms 589652 KB Output is correct
53 Correct 257 ms 590416 KB Output is correct
54 Correct 273 ms 590232 KB Output is correct
55 Correct 258 ms 590328 KB Output is correct
56 Correct 251 ms 590240 KB Output is correct
57 Correct 275 ms 590216 KB Output is correct
58 Correct 255 ms 590164 KB Output is correct
59 Correct 249 ms 589904 KB Output is correct
60 Correct 242 ms 589908 KB Output is correct
61 Correct 1559 ms 854240 KB Output is correct
62 Runtime error 1038 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -