oj.uz

Submission #928836

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

vector<short> b[2505][2505];
vector<short> c[2505][2505];
vector<pair<short,short>> d[2505][2505];
vector<pair<short,short>> e[2505][2505];
short lef[2505][2505];
short rig[2505][2505];
short up[2505][2505];
short down[2505][2505];
long long v[2500*2500];

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);
		}
	}
	std::vector<vector<int>>().swap(a);
	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());
			std::vector<short>().swap(b[i][j]);

		}
	}
	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());
			std::vector<short>().swap(c[i][j]);

		}
	}
	int nn = 0;
	for(int i = 1 ; i<n-1 ; i++){
		for(int j=1 ; j<m-1 ; j++){
			short x = lef[i][j];
			short y = rig[i][j];
			short z = up[i][j];
			short w = down[i][j];
			v[++nn]=x + 2501ll*y + 2501ll*2501ll*z+2501ll*2501*2501*w;
			
		}
	}
	sort(v+1,v+nn+1);

	for(int i=1 ; i<=nn ; i++){
		if(v[i]==v[i-1])continue;
	
		
		int x = v[i]%2501;
		int y = v[i]/2501%2501;
		int z = v[i]/2501/2501%2501;
		int w = v[i]/2501/2501/2501%2501;
	
		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(),(pair<short,short>){z+1,32767});
			if(k== d[x+1][y-1].begin())continue;
	
			if((--k)->second <w-1)continue;
			
			
			auto t = upper_bound(e[z+1][w-1].begin(),e[z+1][w-1].end(),(pair<short,short>){x+1,32767});
			
			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 156 ms 599380 KB Output is correct
2 Correct 129 ms 599380 KB Output is correct
3 Correct 130 ms 599276 KB Output is correct
4 Correct 129 ms 599380 KB Output is correct
5 Correct 130 ms 599492 KB Output is correct
6 Correct 131 ms 599708 KB Output is correct
7 Correct 145 ms 599380 KB Output is correct
8 Correct 130 ms 599380 KB Output is correct
9 Correct 131 ms 599380 KB Output is correct
10 Correct 130 ms 599376 KB Output is correct
11 Correct 129 ms 599344 KB Output is correct
12 Correct 142 ms 599396 KB Output is correct
13 Correct 130 ms 591188 KB Output is correct
14 Correct 134 ms 595284 KB Output is correct
15 Correct 131 ms 599248 KB Output is correct
16 Correct 130 ms 599420 KB Output is correct
17 Correct 130 ms 591184 KB Output is correct
18 Correct 133 ms 595196 KB Output is correct
19 Correct 142 ms 599380 KB Output is correct
20 Correct 141 ms 599380 KB Output is correct
21 Correct 129 ms 595372 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 599380 KB Output is correct
2 Correct 129 ms 599380 KB Output is correct
3 Correct 130 ms 599276 KB Output is correct
4 Correct 129 ms 599380 KB Output is correct
5 Correct 130 ms 599492 KB Output is correct
6 Correct 131 ms 599708 KB Output is correct
7 Correct 145 ms 599380 KB Output is correct
8 Correct 130 ms 599380 KB Output is correct
9 Correct 131 ms 599380 KB Output is correct
10 Correct 130 ms 599376 KB Output is correct
11 Correct 129 ms 599344 KB Output is correct
12 Correct 142 ms 599396 KB Output is correct
13 Correct 130 ms 591188 KB Output is correct
14 Correct 134 ms 595284 KB Output is correct
15 Correct 131 ms 599248 KB Output is correct
16 Correct 130 ms 599420 KB Output is correct
17 Correct 130 ms 591184 KB Output is correct
18 Correct 133 ms 595196 KB Output is correct
19 Correct 142 ms 599380 KB Output is correct
20 Correct 141 ms 599380 KB Output is correct
21 Correct 129 ms 595372 KB Output is correct
22 Correct 131 ms 599544 KB Output is correct
23 Correct 132 ms 599632 KB Output is correct
24 Correct 132 ms 599632 KB Output is correct
25 Correct 137 ms 599720 KB Output is correct
26 Correct 143 ms 599456 KB Output is correct
27 Correct 133 ms 599588 KB Output is correct
28 Correct 131 ms 599664 KB Output is correct
29 Correct 131 ms 599376 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 599380 KB Output is correct
2 Correct 129 ms 599380 KB Output is correct
3 Correct 130 ms 599276 KB Output is correct
4 Correct 129 ms 599380 KB Output is correct
5 Correct 130 ms 599492 KB Output is correct
6 Correct 131 ms 599708 KB Output is correct
7 Correct 145 ms 599380 KB Output is correct
8 Correct 130 ms 599380 KB Output is correct
9 Correct 131 ms 599380 KB Output is correct
10 Correct 130 ms 599376 KB Output is correct
11 Correct 129 ms 599344 KB Output is correct
12 Correct 142 ms 599396 KB Output is correct
13 Correct 130 ms 591188 KB Output is correct
14 Correct 134 ms 595284 KB Output is correct
15 Correct 131 ms 599248 KB Output is correct
16 Correct 130 ms 599420 KB Output is correct
17 Correct 131 ms 599544 KB Output is correct
18 Correct 132 ms 599632 KB Output is correct
19 Correct 132 ms 599632 KB Output is correct
20 Correct 137 ms 599720 KB Output is correct
21 Correct 143 ms 599456 KB Output is correct
22 Correct 133 ms 599588 KB Output is correct
23 Correct 131 ms 599664 KB Output is correct
24 Correct 131 ms 599376 KB Output is correct
25 Correct 130 ms 591184 KB Output is correct
26 Correct 133 ms 595196 KB Output is correct
27 Correct 142 ms 599380 KB Output is correct
28 Correct 141 ms 599380 KB Output is correct
29 Correct 129 ms 595372 KB Output is correct
30 Correct 133 ms 610388 KB Output is correct
31 Correct 138 ms 610388 KB Output is correct
32 Correct 146 ms 610440 KB Output is correct
33 Correct 137 ms 610196 KB Output is correct
34 Correct 142 ms 610484 KB Output is correct
35 Runtime error 2798 ms 1048576 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 599380 KB Output is correct
2 Correct 129 ms 599380 KB Output is correct
3 Correct 130 ms 599276 KB Output is correct
4 Correct 129 ms 599380 KB Output is correct
5 Correct 130 ms 599492 KB Output is correct
6 Correct 131 ms 599708 KB Output is correct
7 Correct 145 ms 599380 KB Output is correct
8 Correct 130 ms 599380 KB Output is correct
9 Correct 131 ms 599380 KB Output is correct
10 Correct 130 ms 599376 KB Output is correct
11 Correct 129 ms 599344 KB Output is correct
12 Correct 142 ms 599396 KB Output is correct
13 Correct 130 ms 591188 KB Output is correct
14 Correct 134 ms 595284 KB Output is correct
15 Correct 131 ms 599248 KB Output is correct
16 Correct 130 ms 599420 KB Output is correct
17 Correct 131 ms 599544 KB Output is correct
18 Correct 132 ms 599632 KB Output is correct
19 Correct 132 ms 599632 KB Output is correct
20 Correct 137 ms 599720 KB Output is correct
21 Correct 143 ms 599456 KB Output is correct
22 Correct 133 ms 599588 KB Output is correct
23 Correct 131 ms 599664 KB Output is correct
24 Correct 131 ms 599376 KB Output is correct
25 Correct 133 ms 610388 KB Output is correct
26 Correct 138 ms 610388 KB Output is correct
27 Correct 146 ms 610440 KB Output is correct
28 Correct 137 ms 610196 KB Output is correct
29 Correct 142 ms 610484 KB Output is correct
30 Runtime error 2798 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 599632 KB Output is correct
2 Correct 147 ms 599604 KB Output is correct
3 Correct 144 ms 599416 KB Output is correct
4 Correct 129 ms 595228 KB Output is correct
5 Correct 140 ms 599556 KB Output is correct
6 Correct 140 ms 599632 KB Output is correct
7 Correct 142 ms 599616 KB Output is correct
8 Correct 143 ms 599884 KB Output is correct
9 Correct 140 ms 599492 KB Output is correct
10 Correct 140 ms 595400 KB Output is correct
11 Correct 138 ms 595372 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 591184 KB Output is correct
2 Correct 133 ms 595196 KB Output is correct
3 Correct 142 ms 599380 KB Output is correct
4 Correct 141 ms 599380 KB Output is correct
5 Correct 129 ms 595372 KB Output is correct
6 Correct 149 ms 599448 KB Output is correct
7 Correct 635 ms 674668 KB Output is correct
8 Correct 1231 ms 747748 KB Output is correct
9 Runtime error 3509 ms 1048576 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 599380 KB Output is correct
2 Correct 129 ms 599380 KB Output is correct
3 Correct 130 ms 599276 KB Output is correct
4 Correct 129 ms 599380 KB Output is correct
5 Correct 130 ms 599492 KB Output is correct
6 Correct 131 ms 599708 KB Output is correct
7 Correct 145 ms 599380 KB Output is correct
8 Correct 130 ms 599380 KB Output is correct
9 Correct 131 ms 599380 KB Output is correct
10 Correct 130 ms 599376 KB Output is correct
11 Correct 129 ms 599344 KB Output is correct
12 Correct 142 ms 599396 KB Output is correct
13 Correct 130 ms 591188 KB Output is correct
14 Correct 134 ms 595284 KB Output is correct
15 Correct 131 ms 599248 KB Output is correct
16 Correct 130 ms 599420 KB Output is correct
17 Correct 131 ms 599544 KB Output is correct
18 Correct 132 ms 599632 KB Output is correct
19 Correct 132 ms 599632 KB Output is correct
20 Correct 137 ms 599720 KB Output is correct
21 Correct 143 ms 599456 KB Output is correct
22 Correct 133 ms 599588 KB Output is correct
23 Correct 131 ms 599664 KB Output is correct
24 Correct 131 ms 599376 KB Output is correct
25 Correct 133 ms 610388 KB Output is correct
26 Correct 138 ms 610388 KB Output is correct
27 Correct 146 ms 610440 KB Output is correct
28 Correct 137 ms 610196 KB Output is correct
29 Correct 142 ms 610484 KB Output is correct
30 Runtime error 2798 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -