Submission #197758

#	Time	Username	Problem	Language	Result	Execution time	Memory
197758		Minnakhmetov	Rectangles (IOI19_rect)	C++14	0 / 100	280 ms	295416 KiB

rect

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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 2505;
int stk[N], to_l[N], to_r[N], w[N], last_v[N][N], 
	last_h[N][N], c_v[N][N], c_h[N][N], t[N];
vector<int> lt[N][N], up[N][N];
pair<int, int> ls[N];

void upd(int x, int y) {
	for (; x < N; x |= x + 1)
		t[x] += y;
}

int que(int x) {
	int s = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		s += t[x];
	return s;
}

void handle(int len) {
	fill(to_l, to_l + len, -1);
	fill(to_r, to_r + len, -1);

	int z = 0;

	for (int i = 0; i < len; i++) {
		while (z > 0 && w[stk[z - 1]] <= w[i]) {
			to_r[stk[--z]] = i;
		}
		stk[z++] = i;
	}

	z = 0;

	for (int i = len - 1; i >= 0; i--) {
		while (z > 0 && w[stk[z - 1]] <= w[i]) {
			to_l[stk[--z]] = i;
		}
		stk[z++] = i;
	}
}

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			w[j] = a[i][j];
		handle(m);
		for (int j = 0; j < m; j++) {
			if (to_l[j] != -1 && to_l[j] + 1 < j) {
				lt[i][j - 1].push_back(to_l[j] + 1);
			}
			if (to_r[j] != -1 && to_l[to_r[j]] != j && j + 1 < to_r[j]) {
				lt[i][to_r[j] - 1].push_back(j + 1);
			}
		}
	}

	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			w[i] = a[i][j];
		}
		handle(n);
		for (int i = 0; i < n; i++) {
			if (to_l[i] != -1 && to_l[i] + 1 < i) {
				up[i - 1][j].push_back(to_l[i] + 1);
			}
			if (to_r[i] != -1 && to_l[to_r[i]] != i && i + 1 < to_r[i]) {
				up[to_r[i] - 1][j].push_back(i + 1);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			last_v[i][j] = -1;
			last_h[i][j] = -1;
		}
	}

	ll ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int x : lt[i][j]) {
				if (last_v[j][x] != i - 1)
					c_v[j][x] = 0;
				last_v[j][x] = i;
				c_v[j][x]++;
			}

			for (int x : up[i][j]) {
				if (last_h[i][x] != j - 1)
					c_h[i][x] = 0;
				last_h[i][x] = j;
				c_h[i][x]++;
			}

			if (lt[i][j].empty())
				continue;

			sort(all(lt[i][j]));

			int p_lt = lt[i][j].size() - 1;

			int z = 0;

			for (int x : up[i][j]) {
				ls[z++] = {j - c_h[i][x] + 1, i};
			}

			sort(ls, ls + z);

			for (int k = z - 1; k >= 0; k--) {
				while (p_lt >= 0 && lt[i][j][p_lt] >= ls[k].first) {
					upd(i - c_v[j][lt[i][j][p_lt]] + 1, 1);
					p_lt--;
				}
				ans += que(ls[k].second);
			}

			for (int x : lt[i][j]) {
				upd(i - c_v[j][lt[i][j][x]] + 1, -1);
			}
		}
	}

	return ans;
}

• 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