Submission #406844

#	Time	Username	Problem	Language	Result	Execution time	Memory
406844		ngrace	Rectangles (IOI19_rect)	C++14	50 / 100	5093 ms	856484 KiB

rect

#include "rect.h"
#include <vector>
#include <iostream>
#include <set>
#include <stack>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second

struct gPair{
	int l, u;//lower and upper vals
	int rc;//row or column
};

long long count_rectangles(std::vector<std::vector<int> > a) {
	long long out=0;
	int R=a.size();
	int C=a[0].size();

	//start by getting good pairs
	v<gPair> rpairs;
	for(int r=1;r<R-1;r++){
		v<int> left(C,-1);
		v<int> right(C,-1);
		stack<int> s;
		for(int c=0;c<C;c++){
			while(s.size()>0 && a[r][s.top()]<=a[r][c]) s.pop();//go back till reach cell to left with greater than cur
			if(s.size()>0) left[c] = s.top();//if cell to left exists then take
			s.push(c);
		}
		s=stack<int>();
		for(int c=C-1;c>=0;c--){
			while(s.size()>0 && a[r][s.top()]<=a[r][c]) s.pop();//go forward till reach cell to right with greater than cur
			if(s.size()>0) right[c] = s.top();//if cell to right exists then take
			s.push(c);
		}

		for(int c=0;c<C;c++){
			if(left[c]!=-1 && right[c]!=-1){
				rpairs.push_back({left[c],right[c],r});
			}
		}
	}

	v<gPair> cpairs;
	for(int c=1;c<C-1;c++){
		v<int> low(R,-1);
		v<int> high(R,-1);
		stack<int> s;
		for(int r=0;r<R;r++){
			while(s.size()>0 && a[s.top()][c]<=a[r][c]) s.pop();//go lower till reach cell lower (up) with greater than cur
			if(s.size()>0) low[r] = s.top();//if cell lower exists then take
			s.push(r);
		}
		s=stack<int>();
		for(int r=R-1;r>=0;r--){
			while(s.size()>0 && a[s.top()][c]<=a[r][c]) s.pop();//go higher till reach cell higher with greater than cur
			if(s.size()>0) high[r] = s.top();//if cell higher exists then take
			s.push(r);
		}

		for(int r=0;r<R;r++){
			if(low[r]!=-1 && high[r]!=-1){
				cpairs.push_back({low[r],high[r],c});
			}
		}
	}

	//pairs are now initialized
	v<v<set<int>>> rows(R,v<set<int>>(C));
	v<v<set<int>>> cols(R,v<set<int>>(C));
	for(gPair g:rpairs){
		//cout<<g.rc<<" "<<g.l<<" "<<g.u<<endl;
		cols[g.rc][g.l+1].insert(g.u-1);//the different columns ahead this cell can get to
	}
	//cout<<endl;
	for(gPair g:cpairs){
		//cout<<g.rc<<" "<<g.l<<" "<<g.u<<endl;
		rows[g.l+1][g.rc].insert(g.u-1);//the differenc rows ahead this cell can get to
	}
	
	//check rows and cols ahead
	/**
	for(int r=0;r<R;r++){
		for(int c=0;c<C;c++){
			cout<<r<<" "<<c<<":"<<endl;
			for(int it : rows[r][c]){
				cout<<it<<" ";
			}
			cout<<endl;
			for(int it : cols[r][c]){
				cout<<it<<" ";
			}
			cout<<endl;
		}
	}**/

	//now try every cell as top left:
	for(int r=1;r<R-1;r++){
		for(int c=1;c<C-1;c++){
			for(int rr:rows[r][c]){
				for(int cc:cols[r][c]){
					//cout<<r<<" "<<c<<" "<<rr<<" "<<cc<<endl;
					bool works=true;
					for(int x=r;x<=rr;x++){
						//for each along left side check if the far col is = cc
						if(cols[x][c].find(cc)==cols[x][c].end()){
							works=false;
							break;
						}
					}
					for(int x=c;x<=cc;x++){
						//for each along left side check if the far col is = cc
						if(rows[r][x].find(rr)==rows[r][x].end() || !works){
							works=false;
							break;
						}
					}

					if(works){
						out++;
					}
				}
			}
		}
	}

	return out;
}

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