Submission #429430

#	Time	Username	Problem	Language	Result	Execution time	Memory
429430		dreezy	Rectangles (IOI19_rect)	C++17	0 / 100	224 ms	295108 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair

const int maxn = 2.5e3 + 5 ;
vector<pi> rightedges[maxn][maxn];//col row
vector<pi> bottomedges[maxn][maxn];//row col

long long count_rectangles(vector<vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	
	
	
	for(int row = 1; row < n -1; row++){
		stack<int> stck;
		stck.push(0);
		//the stack is always in decreasing order
		//we keep track of what indices work and which ones don't
		for(int col = 1; col <m ; col++){
			while(stck.size()){
				if(stck.top() != col -1){
					rightedges[row][stck.top() +1].pb({col -1, row});
				}
				
				if(a[row][stck.top()] < a[row][col]){
					//if the current cell is taller than the left edge, then no rectangles can be made
					//from left past the current cell
					stck.pop();
				}
				else {
					
					if (a[row][stck.top()] == a[row][col]){
						stck.pop();
					}
					break;
				}
				//else, left is taller than curcell
				//this means that we can build more rectangles
			}
			stck.push(col);
		}
	}
	/*
	for(int row = 1; row < n -1; row++){
		for(int col = 1; col <m ; col++){
			cout << row<<", "<<col<<": ";
			for(pi p : rightedges[row][col])
				cout << p.second<<", "<<p.first<<";";
			cout <<endl;
		}
	}*/
	
	for(int col = 1; col < m -1; col++){
		stack<int> stck;
		stck.push(0);
		//the stack is always in decreasing order
		//we keep track of what indices work and which ones don't
		for(int row = 1; row <n ; row++){
			while(stck.size()){
				if(stck.top() != row -1){
					bottomedges[stck.top() +1][col].pb({row - 1, col});
				}
				
				if(a[stck.top()][col] < a[row][col]){
					//if the current cell is taller than the left edge, then no rectangles can be made
					//from left past the current cell
					stck.pop();
				}
				else {
					
					if (a[stck.top()][col] == a[row][col]){
						stck.pop();
					}
					break;
				}
				//else, left is taller than curcell
				//this means that we can build more rectangles
			}
			stck.push(row);
		}
	}
	/*for(int row = 1; row < n; row++){
		for(int col = 1; col <m -1; col++){
			cout << row<<", "<<col<<": ";
			for(pi p : bottomedges[row][col])
				cout << p.first<<", "<<p.second<<";";
			cout <<endl;
		}
	}*/
	
	for(int row = n -2; row >0; row--){
		for(int col = m-2; col >0; col--){
			//int row_size 
			
			for(int i =0; i<rightedges[row][col].size(); i++){
				
				auto it = lower_bound(rightedges[row+1][col].begin(), rightedges[row+1][col].end(),mp(rightedges[row][col][i].f, -1));
				if(it != rightedges[row + 1][col].end() and it->f == rightedges[row][col][i].f)
					rightedges[row][col][i].s = it ->s;
			}
			
			for(int i =0; i<bottomedges[row][col].size(); i++){
				
				auto it = lower_bound(bottomedges[row][col+1].begin(), bottomedges[row][col+1].end(),mp(bottomedges[row][col][i].f, -1));
				if(it != bottomedges[row][col+1].end() and it->f == bottomedges[row][col][i].f)
					bottomedges[row][col][i].s = it ->s;
			}
		}
	}
	
	ll ans = 0;

	for(int row = 1; row< n -1; row++){
		for(int col = 1; col < n-1; col++){
		
			for(int r = 0; r < rightedges[row][col].size(); r++){
				for(int c = 0; c< bottomedges[row][col].size(); c++){
					/*if(row == 1 and col == 1){
						cout << rightedges[row][col][r].s<<", "<<rightedges[row][col][r].f<<":::";
						cout << bottomedges[row][col][c].f<<", "<<bottomedges[row][col][c].s<<endl;
					}*/
					if(rightedges[row][col][r].s <= bottomedges[row][col][c].f){
						//if(rightedges[row][col][r].s == bottomedges[row][col][c].f){
							ans++;
							//cout << row<<", "<<col<<": ";
							//cout << bottomedges[row][col][c].f<<", "<<bottomedges[row][col][c].s<<endl;
						}
				}
			}
		}
	}


	
	return ans;
}

/**************/

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for(int i =0; i<rightedges[row][col].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for(int i =0; i<bottomedges[row][col].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |    for(int r = 0; r < rightedges[row][col].size(); r++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:125:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int c = 0; c< bottomedges[row][col].size(); c++){
      |                    ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28