Submission #518450

#	Time	Username	Problem	Language	Result	Execution time	Memory
518450		sidon	Rectangles (IOI19_rect)	C++17	100 / 100	3384 ms	586448 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], d[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]); int add = 0;
	for(auto &u : {c, d}) {
		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] + add) --sR;
					u[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(u[1][C(i, j)], u[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] + add) --sR;
					u[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(u[3][C(i, j)], u[3][C(n-1-i, j)]);
		}
		++add;
	}

	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({d[0][i], d[1][i], d[2][i], d[3][i]}) >= 0)
			q.push_back({d[0][i], m-1-d[1][i], d[2][i], n-1-d[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: 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