oj.uz

Submission #928844

# Submission time Handle Problem Language Result Execution time Memory
928844 2024-02-17T06:42:35 Z knon0501 Rectangles (IOI19_rect) C++14
0 / 100
 198 ms 599664 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

vector<short> b[2505][2505];
vector<short> c[2505][2505];
vector<int> d[2505][2505];
vector<int> e[2505][2505];
short lef[2505][2505];
short rig[2505][2505];
short up[2505][2505];
short down[2505][2505];
long long v[2501*2501];

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*2501+y);
					y=x;
				}
				prv=x;
			}
			if(prv>=0){

				d[i][j].push_back(prv*2501+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*2501+y);
					y=x;
				}
				prv=x;
			}
			if(prv>=0){
			
				e[i][j].push_back(prv*2501+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(),(z+1)*2501+2500);
			if(k== d[x+1][y-1].begin())continue;
	
			if(*(--k) <w-1)continue;
			
			
			auto t = upper_bound(e[z+1][w-1].begin(),e[z+1][w-1].end(),(z+1)*2501+2500);
			
			if(t== e[z+1][w-1].begin())continue;
			
			if(*(--t) <y-1)continue;
			ans++;
	}
	return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:158:31: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  158 |     e[i][j].push_back(prv*2501+y);
      |                       ~~~~~~~~^~
rect.cpp:136:31: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |     d[i][j].push_back(prv*2501+y);
      |                       ~~~~~~~~^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 599420 KB Output is correct
2 Correct 131 ms 599376 KB Output is correct
3 Correct 130 ms 599376 KB Output is correct
4 Correct 143 ms 599300 KB Output is correct
5 Correct 133 ms 599380 KB Output is correct
6 Incorrect 131 ms 599460 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 599420 KB Output is correct
2 Correct 131 ms 599376 KB Output is correct
3 Correct 130 ms 599376 KB Output is correct
4 Correct 143 ms 599300 KB Output is correct
5 Correct 133 ms 599380 KB Output is correct
6 Incorrect 131 ms 599460 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 599420 KB Output is correct
2 Correct 131 ms 599376 KB Output is correct
3 Correct 130 ms 599376 KB Output is correct
4 Correct 143 ms 599300 KB Output is correct
5 Correct 133 ms 599380 KB Output is correct
6 Incorrect 131 ms 599460 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 599420 KB Output is correct
2 Correct 131 ms 599376 KB Output is correct
3 Correct 130 ms 599376 KB Output is correct
4 Correct 143 ms 599300 KB Output is correct
5 Correct 133 ms 599380 KB Output is correct
6 Incorrect 131 ms 599460 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 599516 KB Output is correct
2 Correct 138 ms 599476 KB Output is correct
3 Correct 143 ms 599416 KB Output is correct
4 Correct 134 ms 595280 KB Output is correct
5 Incorrect 141 ms 599664 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 599456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 599420 KB Output is correct
2 Correct 131 ms 599376 KB Output is correct
3 Correct 130 ms 599376 KB Output is correct
4 Correct 143 ms 599300 KB Output is correct
5 Correct 133 ms 599380 KB Output is correct
6 Incorrect 131 ms 599460 KB Output isn't correct
7 Halted 0 ms 0 KB -