Submission #170713

#	Time	Username	Problem	Language	Result	Execution time	Memory
170713		youngyojun	Rectangles (IOI19_rect)	C++17	100 / 100	4386 ms	747564 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define fi first
#define se second
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

struct NOD {
	NOD(int sy, int sx, int ey, int ex)
		: sy(sy), sx(sx), ey(ey), ex(ex) {}
	int sy, sx, ey, ex;
	
	void f(int &_sy, int &_sx, int &_ey, int &_ex) const {
		_sy = sy; _sx = sx; _ey = ey; _ex = ex;
	}
	bool operator < (const NOD &t) const {
		if(sy != t.sy) return sy < t.sy;
		if(sx != t.sx) return sx < t.sx;
		if(ey != t.ey) return ey < t.ey;
		return ex < t.ex;
	}
	bool operator == (const NOD &t) const {
		return sy == t.sy && sx == t.sx && ey == t.ey && ex == t.ex;
	}
};

const int MX = 4096;
struct SEG {
	SEG() { init(); }
	int d[MX*2];

	void init() { fill(d, d+MX*2, INF); }
	void upd(int x, int r) { upmin(d[x+MX], r); }
	void cal() { for(int i = MX; i--;) d[i] = min(d[i<<1], d[i<<1|1]); }
	int get(int s, int e) {
		int r = INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
			if(s&1) upmin(r, d[s++]);
			if(~e&1) upmin(r, d[e--]);
		}
		return r;
	}
} segu[2505], segd[2505], segl[2505], segr[2505];

vector<NOD> NV;

int myu[2505][2505], myd[2505][2505], myl[2505][2505], myr[2505][2505];
int cou[2505][2505], cod[2505][2505], col[2505][2505], cor[2505][2505];

int A[2505][2505];
int H, W, Ans;

int solve() {
	for(int j = 0; j < W; j++) {
		vector<pii> V; V.eb(-1, INF);
		for(int i = 0, h; i < H; i++) {
			for(h = A[i][j]; V.back().se <= h; V.pop_back());
			myu[i][j] = V.back().fi;
			V.eb(i, h);
		}
		V.clear(); V.eb(H, INF);
		for(int i = H, h; i--;) {
			for(h = A[i][j]; V.back().se <= h; V.pop_back());
			myd[i][j] = V.back().fi;
			V.eb(i, h);
		}
		V.clear(); V.eb(-1, INF);
		for(int i = 0, h; i < H; i++) {
			for(h = A[i][j]; V.back().se < h; V.pop_back());
			cou[i][j] = V.back().fi + 1;
			V.eb(i, h);
		}
		V.clear(); V.eb(H, INF);
		for(int i = H, h; i--;) {
			for(h = A[i][j]; V.back().se < h; V.pop_back());
			cod[i][j] = V.back().fi - 1;
			V.eb(i, h);
		}
	}
	for(int i = 0; i < H; i++) {
		vector<pii> V; V.eb(-1, INF);
		for(int j = 0, h; j < W; j++) {
			for(h = A[i][j]; V.back().se <= h; V.pop_back());
			myl[i][j] = V.back().fi;
			V.eb(j, h);
		}
		V.clear(); V.eb(W, INF);
		for(int j = W, h; j--;) {
			for(h = A[i][j]; V.back().se <= h; V.pop_back());
			myr[i][j] = V.back().fi;
			V.eb(j, h);
		}
		V.clear(); V.eb(-1, INF);
		for(int j = 0, h; j < W; j++) {
			for(h = A[i][j]; V.back().se < h; V.pop_back());
			col[i][j] = V.back().fi + 1;
			V.eb(j, h);
		}
		V.clear(); V.eb(W, INF);
		for(int j = W, h; j--;) {
			for(h = A[i][j]; V.back().se < h; V.pop_back());
			cor[i][j] = V.back().fi - 1;
			V.eb(j, h);
		}
	}

	for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
		segu[i].upd(j, -cou[i][j]);
		segd[i].upd(j, cod[i][j]);
		segl[j].upd(i, -col[i][j]);
		segr[j].upd(i, cor[i][j]);
	}
	for(int i = 0; i < H; i++) { segu[i].cal(); segd[i].cal(); }
	for(int i = 0; i < W; i++) { segl[i].cal(); segr[i].cal(); }

	for(int i = 1; i < H-1; i++) for(int j = 1; j < W-1; j++) {
		int sy = myu[i][j] + 1, sx = myl[i][j] + 1, ey = myd[i][j] - 1, ex = myr[i][j] - 1;
		if(!sy || !sx || H-1 == ey || W-1 == ex) continue;
		NV.eb(sy, sx, ey, ex);
	}
	sorv(NV); univ(NV);

	for(auto &hubo : NV) {
		int sy, sx, ey, ex; hubo.f(sy, sx, ey, ex);
		if(sy < -segu[ey+1].get(sx, ex)) continue;
		if(segd[sy-1].get(sx, ex) < ey) continue;
		if(sx < -segl[ex+1].get(sy, ey)) continue;
		if(segr[sx-1].get(sy, ey) < ex) continue;
		Ans++;
	}
	return Ans;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	::H = sz(a); ::W = sz(a[0]);
	for(int i = 0; i < ::H; i++) for(int j = 0; j < ::W; j++)
		::A[i][j] = a[i][j];
	return solve();
}

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