Submission #424930

#	Time	Username	Problem	Language	Result	Execution time	Memory
424930		alishahali1382	Rectangles (IOI19_rect)	C++14	15 / 100	5044 ms	86992 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()

const int inf=1000001000; // 1e9
const ll INF=10000000010000000; // 1e16
const int mod=1000000007;
const int N=2510;

ll ans; // :(
int n, m, k, x, y, u, v, t;
int A[N][N];
int L[N][N], R[N][N], U[N][N], D[N][N];
vector<pii> vec[N];
int dwn[N][N<<1];

ll count_rectangles(vector<vector<int>> _A){
	n=SZ(_A);
	m=SZ(_A[0]);
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) A[i][j]=_A[i-1][j-1];
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++) for (L[i][j]=j-1; L[i][j] && A[i][L[i][j]]<A[i][j]; L[i][j]=L[i][L[i][j]]) ;
		for (int j=m; j; j--) for (R[i][j]=j+1; R[i][j]<=m && A[i][R[i][j]]<A[i][j]; R[i][j]=R[i][R[i][j]]) ;
	}
	for (int j=1; j<=m; j++){
		for (int i=1; i<=n; i++) for (U[i][j]=i-1; U[i][j] && A[U[i][j]][j]<A[i][j]; U[i][j]=U[U[i][j]][j]) ;
		for (int i=n; i; i--) for (D[i][j]=i+1; D[i][j]<=n && A[D[i][j]][j]<A[i][j]; D[i][j]=D[D[i][j]][j]) ;
	}
	debug("LRDU built")
	for (int u=1; u<n; u++) for (int d=u+2; d<=n; d++)
		for (int l=1; l<m; l++) for (int r=l+2; r<=m; r++){
			int ok=1;
			for (int i=l+1; i<r; i++) ok&=(U[d][i]==u || D[u][i]==d);
			for (int i=u+1; i<d; i++) ok&=(R[i][l]==r || L[i][r]==l);
			ans+=ok;
		}

	return ans;
}

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