Submission #197759

#	Time	Username	Problem	Language	Result	Execution time	Memory
197759		Minnakhmetov	Rectangles (IOI19_rect)	C++14	100 / 100	3255 ms	679168 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, x};
				}

				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 k = p_lt + 1; k < lt[i][j].size(); k++) {
					upd(i - c_v[j][lt[i][j][k]] + 1, -1);
				}
			}
		}

		return ans;
	}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:130:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = p_lt + 1; k < lt[i][j].size(); k++) {
                            ~~^~~~~~~~~~~~~~~~~

• 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