oj.uz

Submission #928773

# Submission time Handle Problem Language Result Execution time Memory
928773 2024-02-17T05:38:13 Z knon0501 Rectangles (IOI19_rect) C++14
10 / 100
 695 ms 703988 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];
vector<vector<int>> aa;
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) {


	aa=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]){
				int x = S.top(); 
			
				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];
			
			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;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:104:9: warning: unused variable 'x' [-Wunused-variable]
  104 |     int x = S.top();
      |         ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 591448 KB Output is correct
2 Correct 276 ms 590288 KB Output is correct
3 Correct 250 ms 590164 KB Output is correct
4 Correct 252 ms 590368 KB Output is correct
5 Correct 301 ms 590376 KB Output is correct
6 Incorrect 245 ms 590400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 591448 KB Output is correct
2 Correct 276 ms 590288 KB Output is correct
3 Correct 250 ms 590164 KB Output is correct
4 Correct 252 ms 590368 KB Output is correct
5 Correct 301 ms 590376 KB Output is correct
6 Incorrect 245 ms 590400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 591448 KB Output is correct
2 Correct 276 ms 590288 KB Output is correct
3 Correct 250 ms 590164 KB Output is correct
4 Correct 252 ms 590368 KB Output is correct
5 Correct 301 ms 590376 KB Output is correct
6 Incorrect 245 ms 590400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 591448 KB Output is correct
2 Correct 276 ms 590288 KB Output is correct
3 Correct 250 ms 590164 KB Output is correct
4 Correct 252 ms 590368 KB Output is correct
5 Correct 301 ms 590376 KB Output is correct
6 Incorrect 245 ms 590400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 590448 KB Output is correct
2 Correct 249 ms 590160 KB Output is correct
3 Correct 251 ms 590332 KB Output is correct
4 Correct 238 ms 589808 KB Output is correct
5 Correct 255 ms 590420 KB Output is correct
6 Correct 252 ms 590164 KB Output is correct
7 Correct 252 ms 590208 KB Output is correct
8 Correct 258 ms 590144 KB Output is correct
9 Correct 252 ms 590164 KB Output is correct
10 Correct 259 ms 589860 KB Output is correct
11 Correct 250 ms 589908 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 589908 KB Output is correct
2 Incorrect 695 ms 703988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 591448 KB Output is correct
2 Correct 276 ms 590288 KB Output is correct
3 Correct 250 ms 590164 KB Output is correct
4 Correct 252 ms 590368 KB Output is correct
5 Correct 301 ms 590376 KB Output is correct
6 Incorrect 245 ms 590400 KB Output isn't correct
7 Halted 0 ms 0 KB -