Submission #154191

#	Time	Username	Problem	Language	Result	Execution time	Memory
154191		wilwxk	Rectangles (IOI19_rect)	C++14	0 / 100	5082 ms	166716 KiB

rect

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

struct cara {
	int h, i, j;
	int xl, xr, yl, yr;
	bool operator<(cara _) const {
		return h<_.h;
	}
};

const int MAXN=2502;
const int INF=1e9+9;
vector<vector<int> > v;
vector<cara> lista;
int table[MAXN][MAXN][4];
int n, m, respf;

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();
			int cur=i*m+j;
			lista[cur].xl=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();
			int cur=i*m+j;
			lista[cur].xr=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();
			int cur=i*m+j;
			lista[cur].yl=st.top().second+1;
			st.push({v[i][j], i});
		}
		while(st.size()) st.pop(); st.push({INF, m});
		for(int i=n-1; i>=0; i--) {
			while(st.top().first<=v[i][j]) st.pop();
			int cur=i*m+j;
			lista[cur].yr=st.top().second-1;
			st.push({v[i][j], i});
		}
	}
}

void upd() {

}
void quy() {

}

int query(int xl, int xr, int yl, int yr, int k) {
	int resp=table[xl][yl][k];
	for(int i=yl; i<=yr; i++) {
		for(int j=xl; j<=xr; j++) {
			if(k==0||k==2) resp=min(resp, table[i][j][k]);
			else resp=max(resp, table[i][j][k]);
		}
	}
	// printf("query %d %d %d %d %d >> %d\n", xl, xr, yl, yr, k, resp);
	return resp;
}

void ativa(int ind) {
	auto cur=lista[ind];
	table[cur.i][cur.j][0]=cur.xl;
	table[cur.i][cur.j][1]=cur.xr;
	table[cur.i][cur.j][2]=cur.yl;
	table[cur.i][cur.j][3]=cur.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.h=v[i][j];
			cur.i=i;
			cur.j=j;
			lista.push_back(cur);
		}
	}
	histogrami();
	histogramj();
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			table[i][j][0]=-1;
			table[i][j][1]=INF;
			table[i][j][2]=-1;
			table[i][j][3]=INF;
		}
	}
	// for(auto cur : lista) printf("(%d, %d): %d %d // %d %d\n", cur.i, cur.j, cur.xl, cur.xr, cur.yl, cur.yr);

	sort(lista.begin(), lista.end());
	for(int i=0; i<lista.size(); i++) {
		// int mxl, mxr, myl, myr; //0, 1, 2, 3
		ativa(i);
		auto cur=lista[i];
		if(query(cur.xl, cur.xr, cur.yl, cur.yr, 0)<cur.xl) continue;
		if(query(cur.xl, cur.xr, cur.yl, cur.yr, 1)>cur.xr) continue;
		if(query(cur.xl, cur.xr, cur.yl, cur.yr, 2)<cur.yl) continue;
		if(query(cur.xl, cur.xr, cur.yl, cur.yr, 3)>cur.yr) continue;
		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:31:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, m});
   ^~~~~
rect.cpp:31: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:43:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, -1});
   ^~~~~
rect.cpp:43: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:50:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, m});
   ^~~~~
rect.cpp:50: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 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<lista.size(); i++) {
               ~^~~~~~~~~~~~~

• 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