Submission #406843

#	Time	Username	Problem	Language	Result	Execution time	Memory
406843		ngrace	Rectangles (IOI19_rect)	C++14	50 / 100	5034 ms	857552 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();

	/**
	bool subSix=true;
	for(int i=0;i<R;i++){//check for sub six
		for(int j=0;j<C;j++){
			if(a[i][j]>1){
				subSix=false;
				break;
			}
		}
		if(!subSix){
			break;
		}
	}

	if(subSix){
		//find sub rectangles with dp[i][j] = {min(dp[i-1][j-1].first, dp[i][j-1].first),
		//										min(dp[i-1][j-1].second, dp[i-1][j].second)}
		//then for each rectangle check the border.
		//can speed up by making so only consider if dp[i-1][j-1].first and dp[i][j-1].first are equal
		v<v<pii>> dp(R,v<pii>(C,{-1,-1}));
		for(int r=1;r<R-1;r++){
			for(int c=1;c<C-1;c++){
				if(a[r][c]==0){
					int f=r;
					int s=c;

					int r1=dp[r-1][c-1].fi;
					int r2=dp[r-1][c].fi;
					int c1=dp[r-1][c-1].se;
					int c2=dp[r][c-1].se;

					if(c1==c2 && c1!=-1){
						s=max(c1,1);
					}
					if(r1==r2 && r1!=-1){
						f=max(r1,1);
					}
					if(c1==-1 && c2!=-1){
						s=c2;
					}
					else if(r1==-1 && r2!=-1){
						f=r2;
					}

					dp[r][c]={f,s};
				}
			}
		}

		//check dp table
		/**for(int r=0;r<R;r++){
			for(int c=0;c<C;c++){
				cout<<"("<<dp[r][c].fi<<" "<<dp[r][c].se<<") ";
			}
			cout<<endl;
		}**/

		//dp table is now made
		//iterate from bottom right to top left
		//for every distinct dp[i][j] value check borders of that rect then mark as covered
		
		/**
		set<pii> checked;
		checked.insert({-1,-1});
		for(int r=R-1;r>0;r--){
			for(int c=C-1;c>0;c--){
				if(a[r][c]==0 && checked.find(dp[r][c])==checked.end()){
					checked.insert(dp[r][c]);
					int r1=dp[r][c].fi;
					int c1=dp[r][c].se;
					bool works=true;
					for(int i=r1;i<=r;i++){
						if(a[i][c1-1]==0 || a[i][c+1]==0){
							works=false;
							break;
						}
					}
					for(int j=c1;j<=c;j++){
						if(a[r1-1][j]==0 || a[r+1][j]==0){
							works=false;
							break;
						}
					}
					if(works){
						out++;
					}
				}
			}
		}
	}
	else if((R<=200 && C<=200) || R<=3){//sub one, two, three and five
		for(int r1=1;r1<R-1;r1++){
			for(int c1=1;c1<C-1;c1++){
				for(int r2=r1;r2<R-1;r2++){
					for(int c2=c1;c2<C-1;c2++){
						//have rect with top left r1, c1, bottom right r2, c2
						//check every value of the rect
						bool works=true;
						for(int r=r1;r<=r2;r++){
							for(int c=c1;c<=c2;c++){
								if(a[r1-1][c]<=a[r][c]){
									works=false;
									break;
								}
								if(a[r2+1][c]<=a[r][c]){
									works=false;
									break;
								}
								if(a[r][c1-1]<=a[r][c]){
									works=false;
									break;
								}
								if(a[r][c2+1]<=a[r][c]){
									works=false;
									break;
								}
							}
							if(!works){
								break;
							}
						}
						if(works){
							out++;
						}
					}
				}
			}
		}
	}**/
	if(false){
		int xass=0;
		xass++;
	}
	else{
		//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;
}

Compilation message (stderr)

rect.cpp:72:3: warning: "/*" within comment [-Wcomment]
   72 |   /**for(int r=0;r<R;r++){
      |

• 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