Submission #158677

#	Time	Username	Problem	Language	Result	Execution time	Memory
158677		LordOfIran	Rectangles (IOI19_rect)	C++14	27 / 100	3343 ms	81400 KiB

rect

#include "rect.h"
//                             In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define ll long long
using namespace std; 

const long long N = 210, OO = 1e12 + 7, M = 1e9 + 7, M2 = 998244353, sq = 360, lg = 23;
typedef pair <ll, ll> pii; 
ll bad[N][N][10], n, m, mn[N][N][N];
vector <vector <int> > a;

void get1(ll i) {
	vector <ll> v;
	for(ll j = 0; j < m; j++) {
		while(v.size()) {
			if(a[i][v[v.size() - 1]] < a[i][j])
				v.pop_back();
			else
				break;
		}
		if(v.size()) 
			bad[i][j][0] = v[v.size() - 1];
		v.pb(j);
	}
	v.clear();
	for(ll j = m - 1; j >= 0; j--) {
		while(v.size()) {
			if(a[i][v[v.size() - 1]] < a[i][j])
				v.pop_back();
			else
				break;	
		}
		if(v.size())
			bad[i][j][1] = v[v.size() - 1];
		else
			bad[i][j][1] = m;
		v.pb(j);
	}
}

void get2(ll j) {
	vector <ll> v;
	for(ll i = 0; i < n; i++) {
		while(v.size()) {
			if(a[v[v.size() - 1]][j] < a[i][j])
				v.pop_back();
			else
				break;	
		}
		if(v.size())
			bad[i][j][2] = v[v.size() - 1];
		v.pb(i);
	}
	v.clear();
	for(ll i = n - 1; i >= 0; i--) {
		while(v.size()) {
			if(a[v[v.size() - 1]][j] < a[i][j])
				v.pop_back();
			else
				break;	
		}
		if(v.size())
			bad[i][j][3] = v[v.size() - 1];
		else
			bad[i][j][3] = n;
		v.pb(i);
	}
}

ll count_rectangles(vector<vector<int> > b) {
	a = b;
	n = (ll)a.size(), m = (ll)a[0].size();
	for(ll i = 0; i < n; i++) 
		get1(i);
	for(ll j = 0; j < m; j++) 
		get2(j);
	for(ll k = 1; k < m; k++) {
		for(ll i = 1; i < n; i++) {
			mn[k][i][i] = bad[i][k][0];
			for(ll j = i + 1; j < n - 1; j++) 
				mn[k][i][j] = max(mn[k][i][j - 1], bad[j][k][0]);
		}
	}
	ll ans = 0;
	for(ll k = 0; k < m - 2; k++) {
		for(ll i = 1; i < n - 1; i++) {
			ll mi = OO;
			for(ll j = i; j < n - 1; j++) {
				mi = min(mi, bad[j][k][1]);
				ll mk = OO, ml = 0; 
				for(ll l = k + 1; l < m - 1; l++) {
					mk = min(mk, bad[i - 1][l][3]);
					ml = max(ml, bad[j + 1][l][2]);
					ll mj = mn[l + 1][i][j];
					if(mj >= k + 1 || mk <= j || ml >= i || mi  <= l)
						continue;
					ans++;
				}
			}
		}
	}
	return ans;
}

• 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