Submission #256809

#	Time	Username	Problem	Language	Result	Execution time	Memory
256809		atoiz	Rectangles (IOI19_rect)	C++14	100 / 100	3219 ms	837336 KiB

rect

#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define x first
#define y second

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 2505;
int R, C, A[MAXN][MAXN];

int prv[MAXN], nxt[MAXN], last[MAXN][MAXN], endp[MAXN][MAXN];
vector<pii> boundLR[MAXN][MAXN], boundUD[MAXN][MAXN];

int bit[MAXN];
void modify(int i, int x) {
	for (; i < MAXN; i += (i & (-i))) bit[i] += x;
}
int get(int i) {
	int ans = 0;
	for (; i > 0; i -= i & (-i)) ans += bit[i];
	return ans;
}

ll count_rectangles(vector<vector<int>> _A) {
	R = (int) _A.size(), C = (int) _A[0].size();
	FOR(i, 1, R) FOR(j, 1, C) A[i][j] = _A[i - 1][j - 1];

	// for each row
	FOR(l, 1, C) FOR(r, l + 2, C) last[l][r] = -1;
	FORB(r, R, 2) {
		prv[1] = 0, nxt[C] = C + 1;
		FOR(c, 2, C) for (prv[c] = c - 1; prv[c] > 0 && A[r][prv[c]] <= A[r][c]; prv[c] = prv[prv[c]]);
		FORB(c, C - 1, 1) for (nxt[c] = c + 1; nxt[c] <= C && A[r][nxt[c]] <= A[r][c]; nxt[c] = nxt[nxt[c]]);
		FOR(c, 1, C) if (1 <= prv[c] && nxt[c] <= C) {
			int c0 = prv[c], c1 = nxt[c];
			if (last[c0][c1] == r) continue;
			if (last[c0][c1] != r + 1) endp[c0][c1] = r + 1;
			last[c0][c1] = r;
			boundLR[r - 1][c0].emplace_back(endp[c0][c1], c1);
		}
	}

	// for each col
	FOR(r0, 1, R) FOR(r1, r0 + 2, R) last[r0][r1] = -1;
	FORB(c, C, 2) {
		prv[1] = 0, nxt[R] = R + 1;
		FOR(r, 2, R) for (prv[r] = r - 1; prv[r] >= 1 && A[prv[r]][c] <= A[r][c]; prv[r] = prv[prv[r]]);
		FORB(r, R - 1, 1) for (nxt[r] = r + 1; nxt[r] <= R && A[nxt[r]][c] <= A[r][c]; nxt[r] = nxt[nxt[r]]);
		FOR(r, 1, R) if (1 <= prv[r] && nxt[r] <= R) {
			int r0 = prv[r], r1 = nxt[r];
			if (last[r0][r1] == c) continue;
			if (last[r0][r1] != c + 1) endp[r0][r1] = c + 1;
			last[r0][r1] = c;
			boundUD[r0][c - 1].emplace_back(r1, endp[r0][r1]);
		}
	}

	ll ans = 0;
	FOR(rootR, 1, R - 2) FOR(rootC, 1, C - 2) if (!boundLR[rootR][rootC].empty() && !boundUD[rootR][rootC].empty()) {
		auto &curLR = boundLR[rootR][rootC], &curUD = boundUD[rootR][rootC];
		sort(curLR.begin(), curLR.end()), sort(curUD.begin(), curUD.end());
		auto itLR = curLR.begin();
		auto itUD = curUD.begin();
		while (itLR != curLR.end() || itUD != curUD.end()) {
			if (itLR != curLR.end() && (itUD == curUD.end() || itLR->x < itUD->x)) {
				ans += get((C + 5) - (itLR++)->second);
			} else {
				modify((C + 5) - (itUD++)->second, 1);
			}
		}
		for (auto p : curUD) modify((C + 5) - p.second, -1);
	}

	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