Submission #826979

#	Time	Username	Problem	Language	Result	Execution time	Memory
826979		vjudge1	Rectangles (IOI19_rect)	C++17	49 / 100	1492 ms	53716 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ll long long
#define pb push_back
#define en '\n'
#define all(v) v.begin(),v.end()
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
const int N = 710;
int a[N][N],n,m;
int Rg[N][N],Lg[N][N],Rh[N][N],Lh[N][N],mxg[N][N][10],mxh[N][N][10],st[N],st1[N];
void buildg(int r) {
	int tek = 1;
	for(int i = 1;i <= m;i++)mxg[r][i][0] = a[r][i];
	st[1] = 0;
	st1[0] = 1;
	for(int j = 1;j < 10;j++) {
		if(tek * 2 > m)break;
		for(int i = 1;i <= m - 2 * tek + 1;i++) {
			mxg[r][i][j] = max(mxg[r][i][j - 1],mxg[r][i + tek][j - 1]);
		}
		tek *= 2;
		st1[j] = tek;
		for(int i = tek;i < min(m + 1,tek * 2);i++)st[i] = j;
	}
}
void buildh(int c) {
	int tek = 1;
	for(int i = 1;i <= n;i++)mxh[c][i][0] = a[i][c];
	st[1] = 0;
	st1[0] = 1;
	for(int j = 1;j < 10;j++) {
		if(tek * 2 > n)break;
		for(int i = 1;i <= n - 2 * tek + 1;i++) {
			mxh[c][i][j] = max(mxh[c][i][j - 1],mxh[c][i + tek][j - 1]);
		}
		tek *= 2;
		st1[j] = tek;
		for(int i = tek;i < min(n + 1,tek * 2);i++)st[i] = j;
	}
}
int getg(int rc,int l,int r) {
	int k = st[r - l + 1];
	return max(mxg[rc][l][k],mxg[rc][r - st1[k] + 1][k]);
}
int geth(int c,int l,int r) {
	int k = st[r - l + 1];
	return max(mxh[c][l][k],mxh[c][r - st1[k] + 1][k]);
}
void build_cell(int x,int y) {
	Rg[x][y] = m;
	Lg[x][y] = 1;
	Rh[x][y] = n;
	Lh[x][y] = 1;
	int l = y + 1,r = m;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(getg(x,y + 1,mid) >= a[x][y]) {
			Rg[x][y] = mid;
			r = mid - 1;
		}else {
			l = mid + 1;
		}
	}
	l = 1,r = y - 1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(getg(x,mid,y - 1) >= a[x][y]) {
			Lg[x][y] = mid;
			l = mid + 1;
		}else {
			r = mid - 1;
		}
	}
	l = x + 1,r = n;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(geth(y,x + 1,mid) >= a[x][y]) {
			Rh[x][y] = mid;
			r = mid - 1;
		}else {
			l = mid + 1;
		}
	}
	l = 1,r = x - 1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(geth(y,mid,x - 1) >= a[x][y]) {
			Lh[x][y] = mid;
			l = mid + 1;
		}else {
			r = mid - 1;
		}
	}
}
int t[N * 4];
vector <int> dob[N];
ll ans;
int Rtemp[N],Ltemp[N];
void build(int v,int tl,int tr) {
	t[v] = 0;
	if(tl == tr)return;
	int tm = (tl + tr) / 2;
	build(v + v,tl,tm);
	build(v + v + 1,tm + 1,tr);
}
void upd(int v,int tl,int tr,int pos) {
	if(tl == tr) {
		t[v]++;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)upd(v + v,tl,tm,pos);
	else upd(v + v + 1,tm + 1,tr,pos);
	t[v] = t[v + v] + t[v + v + 1];
}
int get(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t[v];
	int tm = (tl + tr) / 2;
	return get(v + v,tl,tm,l,r) + get(v + v + 1,tm + 1,tr,l,r);
}
void calc1(int L,int R,int l,int r) {
	if(r - l + 1 < 3 || R - L + 1 < 3)return;
	for(int i = r;i > l + 1;i--)dob[max(l,Ltemp[i])].pb(i);
	for(int i = l;i < r - 1;i++) {
		while(!dob[i].empty()) {
			upd(1,1,m,dob[i].back());
			dob[i].pop_back();
		}
		int curR = min(r,Rtemp[i]);
		ans += get(1,1,m,i + 2,curR);
	}
	dob[r - 1].clear();
	dob[r].clear();
}
void calc(int L) {
	for(int i = 1;i <= m;i++) {
		Rtemp[i] = m;
		Ltemp[i] = 1;
	}
	for(int i = L + 2;i <= n;i++) {
		build(1,1,m);
		int l = 1;
		dob[1].clear();
		Ltemp[1] = max(Ltemp[1],Lg[i - 1][1]);
		Rtemp[1] = min(Rtemp[1],Rg[i - 1][1]);
		for(int j = 2;j <= m;j++) {
			dob[j].clear();
			Ltemp[j] = max(Ltemp[j],Lg[i - 1][j]);
			Rtemp[j] = min(Rtemp[j],Rg[i - 1][j]);
			if(Rh[L][j] < i || Lh[i][j] > L) {
				int r = j;
				calc1(L,i,l,r);
				//cout << L << " " << i << " " << l << " " << r << " " << ans << " " << Ltemp[r] << en;
				l = j;
				continue;
			}
		}
		if(l <= m)calc1(L,i,l,m);
	}
}
ll count_rectangles(vector<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 + 1][j + 1] = A[i][j];
		}
	}
	for(int i = 1;i <= n;i++)buildg(i);
	for(int i = 1;i <= m;i++)buildh(i);
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			build_cell(i,j);
		}
	}
	for(int i = 1;i < n - 1;i++)calc(i);
	return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/

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