Submission #154202

#	Time	Username	Problem	Language	Result	Execution time	Memory
154202		wilwxk	Rectangles (IOI19_rect)	C++14	49 / 100	2778 ms	145272 KiB

rect

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

const int MAXN=705;
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);
}

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

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*n; i++) {
		for(int j=0; j<4*m; j++) {
			seg[0][i][j]=seg[2][i][j]=-1;
			seg[1][i][j]=seg[3][i][j]=MAXN;
		}
	}

	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;
		seg[0][0][0]=seg[2][0][0]=MAXN;
		seg[1][0][0]=seg[3][0][0]=-1;
		qui(1, 1, n, borda[0][i][j], borda[1][i][j], borda[2][i][j], borda[3][i][j]);
		for(int k=0; k<4; k++) {
			if((k&1)&&seg[k][0][0]>borda[k][i][j]) ok=0;  
			if((~k&1)&&seg[k][0][0]<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: 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