Submission #835915

#	Time	Username	Problem	Language	Result	Execution time	Memory
835915		Lobo	Rectangles (IOI19_rect)	C++17	27 / 100	363 ms	58804 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(),x.end()
 
const int maxn = 255;
const int inf = 1e9+10;
const int lg = 11;
int n, m, a[maxn][maxn];
int lf[maxn][maxn], rg[maxn][maxn], up[maxn][maxn], dw[maxn][maxn];
set<pair<pair<int,int>,pair<int,int>>> ans;
 
 
struct {
	int mnr[lg+1][maxn], mxr[lg+1][maxn];
	void build(vector<int> vec) {
		for(int i = 0; i < vec.size(); i++) {
			mnr[0][i] = vec[i];
			mxr[0][i] = vec[i];
		}
 
		for(int b = 1; b <= lg; b++) {
			for(int i = 0; i < vec.size(); i++) {
				mnr[b][i] = min(mnr[b-1][i],mnr[b-1][min((int) vec.size()-1,i+(1<<(b-1)))]);
				mxr[b][i] = max(mxr[b-1][i],mxr[b-1][min((int) vec.size()-1,i+(1<<(b-1)))]);
			}
		}
	}
 
	int qrymn(int l, int r) {
		int b = 31-__builtin_clz(r-l+1);
		return min(mnr[b][l],mnr[b][r-(1<<b)+1]);
	}
	int qrymx(int l, int r) {
		int b = 31-__builtin_clz(r-l+1);
		return max(mxr[b][l],mxr[b][r-(1<<b)+1]);
	}
 
}seglf[maxn], segrg[maxn], segup[maxn], segdw[maxn];
 
int check(int r1, int r2, int c1, int c2) {
	if(c1 > c2 || r1 > r2 || c1 == -1 || c1 == m || c2 == -1 || c2 == m || r1 == -1 || r1 == n || r2 == -1 || r2 == n) return 0;
	if(c1 == 0 || c2 == m-1 || r1 == 0 || r2 == n-1) return 0;
 
	int mxlf = -1; mxlf = seglf[c2+1].qrymx(r1,r2);
	int mnrg = m; mnrg = segrg[c1-1].qrymn(r1,r2);
	int mxup = -1; mxup = segup[r2+1].qrymx(c1,c2);
	int mndw = n; mndw = segdw[r1-1].qrymn(c1,c2);
 
	if(mxlf < c1 && mnrg > c2 && mxup < r1 && mndw > r2) {
		assert(mxlf+1 == c1 || mnrg-1 == c2);
		assert(mxup+1 == r1 || mndw-1 == r2);
		return 1;
	}
	return 0;
}
 
long long count_rectangles(std::vector<std::vector<int>> A) {
	n = A.size();
	m = A[0].size();
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			a[i][j] = A[i][j];
		}
	}
 
	// primeiro >=
	for(int i = 0; i < n; i++) {
		stack<pair<int,int>> stk;
		// left
		for(int j = 0; j < m; j++) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) lf[i][j] = -1;
			else lf[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],j));
		}
 
		while(stk.size()) stk.pop();
 
		// right
		for(int j = m-1; j >= 0; j--) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) rg[i][j] = m;
			else rg[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],j));
		}
	}
 
	for(int j = 0; j < m; j++) {
		stack<pair<int,int>> stk;
		//up
		for(int i = 0; i < n; i++) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) up[i][j] = -1;
			else up[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],i));
		}
 
		while(stk.size()) stk.pop();
 
		// down
		for(int i = n-1; i >= 0; i--) {
			while(stk.size() && stk.top().fr < a[i][j]) stk.pop();
			if(stk.size() == 0) dw[i][j] = n;
			else dw[i][j] = stk.top().sc;
			stk.push(mp(a[i][j],i));
		}
	}
 
	for(int i = 0; i < n; i++) {
		vector<int> vec;
		for(int j = 0; j < m; j++) {
			vec.pb(up[i][j]);
		}
 
		segup[i].build(vec);
 
		vec.clear();
		for(int j = 0; j < m; j++) {
			vec.pb(dw[i][j]);
		}
		segdw[i].build(vec);
	}
 
	for(int j = 0; j < m; j++) {
		vector<int> vec;
		for(int i = 0; i < n; i++) {
			vec.pb(lf[i][j]);
		}
 
		seglf[j].build(vec);
 
		vec.clear();
		for(int i = 0; i < n; i++) {
			vec.pb(rg[i][j]);
		}
		segrg[j].build(vec);
	}
 
	// for(int r1 = 1; r1 < n-1; r1++) {
	// 	for(int r2 = r1; r2 < n-1; r2++) {
	// 		for(int c1 = 1; c1 < m-1; c1++) {
	// 			for(int c2 = c1; c2 < m-1; c2++) {
	// 				if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
	// 			}
	// 		}
	// 	}
	// }
 
	for(int r1 = 1; r1 < n-1; r1++) {
		for(int c1 = 1; c1 < m-1; c1++) {
			int r2,c2;
			r2 = dw[r1-1][c1]-1;
			c2 = rg[r1][c1-1]-1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
 
			r2 = dw[r1-1][c1]-1;
			c2 = rg[r2][c1-1]-1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
			
			c2 = rg[r1][c1-1]-1;
			r2 = dw[r1-1][c2]-1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
		}
	}
 
	for(int r1 = 1; r1 < n-1; r1++) {
		for(int c2 = 1; c2 < m-1; c2++) {
			int r2,c1;
			r2 = dw[r1-1][c2]-1;
			c1 = lf[r1][c2+1]+1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
 
			r2 = dw[r1-1][c2]-1;
			c1 = lf[r2][c2+1]+1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
 
			c1 = lf[r1][c2+1]+1;
			r2 = dw[r1-1][c1]-1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
		}
	}
	for(int r2 = 1; r2 < n-1; r2++) {
		for(int c1 = 1; c1 < m-1; c1++) {
			int r1,c2;
			r1 = up[r2+1][c1]+1;
			c2 = rg[r2][c1-1]-1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
 
			r1 = up[r2+1][c1]+1;
			c2 = rg[r1][c1-1]-1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
 
			c2 = rg[r2][c1-1]-1;
			r1 = up[r2+1][c2]+1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
		}
	}
 
	for(int r2 = 1; r2 < n-1; r2++) {
		for(int c2 = 1; c2 < m-1; c2++) {
			int r1,c1;
			r1 = up[r2+1][c2]+1;
			c1 = lf[r2][c2+1]+1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
 
			r1 = up[r2+1][c2]+1;
			c1 = lf[r1][c2+1]+1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
 
			c1 = lf[r2][c2+1]+1;
			r1 = up[r2+1][c1]+1;
			if(check(r1,r2,c1,c2)) ans.insert(mp(mp(r1,r2),mp(c1,c2)));
		}
	}
 
	return ans.size();
}

Compilation message (stderr)

rect.cpp: In member function 'void<unnamed struct>::build(std::vector<int>)':
rect.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i = 0; i < vec.size(); i++) {
      |                  ~~^~~~~~~~~~~~
rect.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    for(int i = 0; i < vec.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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