Submission #518440

#	Time	Username	Problem	Language	Result	Execution time	Memory
518440		sidon	Rectangles (IOI19_rect)	C++17	10 / 100	54 ms	69704 KiB

rect

#include <bits/stdc++.h>
using namespace std;
#define C(X, Y) ((X)*m+Y)

const int Z = 2500;

struct SegmentTree {
	int S[2*Z];
	void operator()() {
		for(int i = Z; --i; ) S[i] = max(S[2*i], S[2*i+1]);
	}
	int operator()(int l, int r) const {
		int x = -1;
		l += Z, r += Z + 1;
		for(; l < r; l /= 2, r /= 2){
			if(l & 1) x = max(x, S[l++]);
			if(r & 1) x = max(x, S[--r]);
		}
		return x;
	}
} s[4][Z];

int n, m, c[4][Z*Z], ans;
int sL[Z], *sR;
vector<array<int, 4>> q;

long long count_rectangles(vector<vector<int>> a) {
	n = size(a), m = size(a[0]);

	for(int i = 0; i < n; i++) {
		for(int k : {0, 1}) {
			sR = sL;
			for(int j = 0; j < m; j++) {
				while(sL != sR && a[i][sR[-1]] <= a[i][j]) --sR;
				c[k][C(i, j)] = sL == sR ? -1 : sR[-1];
				*sR++ = j;
			}
			reverse(begin(a[i]), end(a[i]));	
		}
		for(int j = 0; j < m-1-j; j++)
			swap(c[1][C(i, j)], c[1][C(i, m-1-j)]);
	}
	for(int j = 0; j < m; j++) {
		for(int k : {2, 3}) {
			sR = sL;
			for(int i = 0; i < n; i++) {
				while(sL != sR && a[sR[-1]][j] <= a[i][j]) --sR;
				c[k][C(i, j)] = sL == sR ? -1 : sR[-1];
				*sR++ = i;
			}
			for(int i = 0; i < n-1-i; i++)
				swap(a[i][j], a[n-1-i][j]);
		}
		for(int i = 0; i < n-1-i; i++)
			swap(c[3][C(i, j)], c[3][C(n-1-i, j)]);
	}

	for(int j = 0; j < m; j++) {
		for(int k : {0, 1}) {
			for(int i = 0; i < n; i++)
				s[k][j].S[i+Z] = c[k][C(i, j)];
			s[k][j]();
		}
	}
	for(int i = 0; i < n; i++) {
		for(int k : {2, 3}) {
			for(int j = 0; j < m; j++)
				s[k][i].S[j+Z] = c[k][C(i, j)];
			s[k][i]();
		}
	}

	q.reserve(n*m);
	for(int i = n*m; --i >=0; ) {
		if(min({c[0][i], c[1][i], c[2][i], c[3][i]}) >= 0)
			q.push_back({c[0][i], m-1-c[1][i], c[2][i], n-1-c[3][i]});
	}
	sort(begin(q), end(q));
	q.resize(unique(begin(q), end(q)) - begin(q));

	for(auto &[j1, j2, i1, i2] : q) {
		if(s[0][j2](i1+1, i2-1) > j1) continue;
		if(s[2][i2](j1+1, j2-1) > i1) continue;

		if(s[1][j1](i1+1, i2-1) > m-1-j2) continue;
		if(s[3][i1](j1+1, j2-1) > n-1-i2) continue;

		++ans;
	}
	return ans;
}

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