Submission #154197

#	Time	Username	Problem	Language	Result	Execution time	Memory
154197		wilwxk	Rectangles (IOI19_rect)	C++14	0 / 100	1075 ms	1048580 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2502;
const int INF=1e9+9;
vector<vector<int> > v;
int borda[4][MAXN][MAXN]; // xl, xr, yl, yr
int seg[4][MAXN*4][MAXN*4];
int n, m, respf;

struct cara {
	int i, j;
	bool operator<(cara _) const {
		return v[i][j]<v[_.i][_.j];
	}
};
vector<cara> lista;

void histogrami() {
	stack<pair<int, int> > st;
	for(int i=0; i<n; i++) {
		while(st.size()) st.pop(); st.push({INF, -1});
		for(int j=0; j<m; j++) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[0][i+1][j+1]=st.top().second+1;
			st.push({v[i][j], j});
		}
		while(st.size()) st.pop(); st.push({INF, m});
		for(int j=m-1; j>=0; j--) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[1][i+1][j+1]=st.top().second-1;
			st.push({v[i][j], j});
		}
	}
}
void histogramj() {
	stack<pair<int, int> > st;
	for(int j=0; j<m; j++) {
		while(st.size()) st.pop(); st.push({INF, -1});
		for(int i=0; i<n; i++) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[2][i+1][j+1]=st.top().second+1;
			st.push({v[i][j], i});
		}
		while(st.size()) st.pop(); st.push({INF, n});
		for(int i=n-1; i>=0; i--) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[3][i+1][j+1]=st.top().second-1;
			st.push({v[i][j], i});
		}
	}
}

void remergej(int ssind, int sind) {
	for(int i=0; i<4; i++) {
		if(i&1) seg[i][ssind][sind]=max(seg[i][ssind][sind*2], seg[i][ssind][sind*2+1]);
		else seg[i][ssind][sind]=min(seg[i][ssind][sind*2], seg[i][ssind][sind*2+1]);
	}
}
void remergei(int ssind, int sind, int ini, int fim, int xind) {
	for(int i=0; i<4; i++) {
		if(i&1) seg[i][ssind][sind]=max(seg[i][ssind*2][sind], seg[i][ssind*2+1][sind]);
		else seg[i][ssind][sind]=min(seg[i][ssind*2][sind], seg[i][ssind*2+1][sind]);
	}
	if(ini==fim) return;
	int mid=(ini+fim)/2;
	if(xind<=mid) remergei(ssind, sind*2, ini, mid, xind);
	else remergei(ssind, sind*2+1, mid+1, fim, xind);
}

void updj(int ssind, int yind, int sind, int ini, int fim, int xind) {
	if(ini==fim) {
		for(int i=0; i<4; i++) seg[i][ssind][sind]=borda[i][yind][xind];
		return;
	}
	int mid=(ini+fim)/2;
	if(xind<=mid) updj(ssind, yind, sind*2, ini, mid, xind);
	else updj(ssind, yind, sind*2+1, mid+1, fim, xind);
	remergej(ssind, sind);
}
void updi(int sind, int ini, int fim, int yind, int xind) {
	if(ini==fim) {
		updj(sind, yind, 1, 1, m, xind);
		return;
	}
	int mid=(ini+fim)/2;
	if(yind<=mid) updi(sind*2, ini, mid, yind, xind);
	else updi(sind*2+1, mid+1, fim, yind, xind);
	remergei(sind, 1, 1, m, xind);
}

int quj(int ssind, int sind, int ini, int fim, int xl, int xr, int k) {
	if(xl<=ini&&xr>=fim) return seg[k][ssind][sind];
	int mid=(ini+fim)/2;
	int resp= k&1 ? -1 : INF;
	if(xl<=mid) {
		if(k&1) resp=max(resp, quj(ssind, sind*2, ini, mid, xl, xr, k));
		else resp=min(resp, quj(ssind, sind*2, ini, mid, xl, xr, k));
	}
	if(xr>mid) {
		if(k&1) resp=max(resp, quj(ssind, sind*2+1, mid+1, fim, xl, xr, k));
		else resp=min(resp, quj(ssind, sind*2+1, mid+1, fim, xl, xr, k));
	}
	return resp;
}
int qui(int sind, int ini, int fim, int xl, int xr, int yl, int yr, int k) {
	if(yl<=ini&&yr>=fim) return quj(sind, 1, 1, m, xl, xr, k);
	int mid=(ini+fim)/2;
	int resp= k&1 ? -1 : INF;
	if(yl<=mid) {
		if(k&1) resp=max(resp, qui(sind*2, ini, mid, xl, xr, yl, yr, k));
		else resp=min(resp, qui(sind*2, ini, mid, xl, xr, yl, yr, k));
	}
	if(yr>mid) {
		if(k&1) resp=max(resp, qui(sind*2+1, mid+1, fim, xl, xr, yl, yr, k));
		else resp=min(resp, qui(sind*2+1, mid+1, fim, xl, xr, yl, yr, k));
	}
	return resp;
}

ll count_rectangles(vector< vector<int> > A) {
	v=A; n=A.size(); m=A[0].size();
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cara cur;
			cur.i=i; cur.j=j;
			lista.push_back(cur);
		}
	}
	histogrami();
	histogramj();
	for(int k=0; k<4; k++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) borda[k][i][j]++;
	
	//1-indexed now
	// for(auto cur : lista) printf("(%d, %d): %d %d // %d %d\n", cur.i, cur.j, cur.xl, cur.xr, cur.yl, cur.yr);

	for(int i=0; i<4*MAXN; i++) {
		for(int j=0; j<4*MAXN; j++) {
			seg[0][i][j]=seg[2][i][j]=INF;
			seg[1][i][j]=seg[3][i][j]=-1;
		}
	}

	sort(lista.begin(), lista.end());
	for(auto cur : lista) {
		int i=cur.i+1; int j=cur.j+1;
		updi(1, 1, n, i, j);
		if(borda[0][i][j]<=1||borda[1][i][j]>=m||borda[2][i][j]<=1||borda[3][i][j]>=n) continue;
		bool ok=1;
		for(int k=0; k<4&&ok; k++) {
			int val=qui(1, 1, n, borda[0][i][j], borda[1][i][j], borda[2][i][j], borda[3][i][j], k);
			if((k&1)&&val>borda[k][i][j]) ok=0;  
			if((~k&1)&&val<borda[k][i][j]) ok=0;  
		}
		if(ok) respf++;
	}

	return respf;
}

Compilation message (stderr)

rect.cpp: In function 'void histogrami()':
rect.cpp:24:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, -1});
   ^~~~~
rect.cpp:24:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, -1});
                              ^~
rect.cpp:30:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, m});
   ^~~~~
rect.cpp:30:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, m});
                              ^~
rect.cpp: In function 'void histogramj()':
rect.cpp:41:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, -1});
   ^~~~~
rect.cpp:41:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, -1});
                              ^~
rect.cpp:47:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, n});
   ^~~~~
rect.cpp:47:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, n});
                              ^~

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