Submission #835928

#	Time	Username	Problem	Language	Result	Execution time	Memory
835928		Lobo	Rectangles (IOI19_rect)	C++17	72 / 100	4621 ms	1048576 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 = 2550;
const int inf = 1e9+10;
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 mn[4*maxn], mx[4*maxn];
	vector<int> vec;
	void build(vector<int> create) {
		vec = create;
		upd(1,0,(int) vec.size()-1);
 
	}
	void upd(int no, int l, int r) {
		if(l == r) {
			mn[no] = mx[no] = vec[l];
			return;
		}
		int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
		upd(lc,l,mid);
		upd(rc,mid+1,r);
		mn[no] = min(mn[lc],mn[rc]);
		mx[no] = max(mx[lc],mx[rc]);
	}
 
	pair<int,int> qry(int no, int l, int r, int ll, int rr) {
		if(l > rr || r < ll) return mp(inf,-inf);
		if(l >= ll && r <= rr) return mp(mn[no],mx[no]);
		int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
		auto ql = qry(lc,l,mid,ll,rr);
		auto qr = qry(rc,mid+1,r,ll,rr);
		return mp(min(ql.fr,qr.fr),max(ql.sc,qr.sc));
	}
 
}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].qry(1,0,n-1,r1,r2).sc;
	// for(int i = r1; i <= r2; i++) mxlf = max(mxlf,lf[i][c2+1]);
	int mnrg = m; mnrg = segrg[c1-1].qry(1,0,n-1,r1,r2).fr;
	// for(int i = r1; i <= r2; i++) mnrg = min(mnrg,rg[i][c1-1]);
	int mxup = -1; mxup = segup[r2+1].qry(1,0,m-1,c1,c2).sc;
	// for(int j = c1; j <= c2; j++) mxup = max(mxup,up[r2+1][j]);
	int mndw = n; mndw = segdw[r1-1].qry(1,0,m-1,c1,c2).fr;
	// for(int j = c1; j <= c2; j++) mndw = min(mndw,dw[r1-1][j]);
 
	if(mxlf < c1 && mnrg > c2 && mxup < r1 && mndw > r2) {
		assert(mxlf+1 == c1 || mnrg-1 == c2);
		assert(mxup+1 == r1 || mndw-1 == r2);
		ans.insert(mp(mp(r1,r2),mp(c1,c2)));
		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;
			check(r1,r2,c1,c2);
			r2 = dw[r1-1][c1]-1;
			c2 = rg[r2][c1-1]-1;
			check(r1,r2,c1,c2);
			c2 = rg[r1][c1-1]-1;
			r2 = dw[r1-1][c2]-1;
			check(r1,r2,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;
			check(r1,r2,c1,c2);
			r2 = dw[r1-1][c2]-1;
			c1 = lf[r2][c2+1]+1;
			check(r1,r2,c1,c2);
			c1 = lf[r1][c2+1]+1;
			r2 = dw[r1-1][c1]-1;
			check(r1,r2,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;
			check(r1,r2,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;
			check(r1,r2,c1,c2);
		}
	}

	return ans.size();
}

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