Submission #823927

#	Time	Username	Problem	Language	Result	Execution time	Memory
823927		dxz05	Rectangles (IOI19_rect)	C++17	100 / 100	4840 ms	653124 KiB

rect

// #pragma GCC optimize("Ofast,O3,unroll-loops")
// #pragma GCC target("avx,avx2")

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

inline vector<pair<int, int>> find_borders(const vector<int> &a){
	int n = (int) a.size();

	stack<int> st;
	vector<int> l(n), r(n);
	for (int i = 0; i < n; i++){
		while (!st.empty() && a[st.top()] < a[i]) st.pop();
		l[i] = (st.empty() ? -1 : st.top());
		st.push(i);
	}

	while (!st.empty()) st.pop();

	for (int i = n - 1; i >= 0; i--){
		while (!st.empty() && a[st.top()] < a[i]) st.pop();
		r[i] = (st.empty() ? n : st.top());
		st.push(i);
	}

	vector<pair<int, int>> ans;
	set<pair<int, int>> s1; // (i, r[i])
	set<pair<int, int>> s2; // (r[i], i)
	for (int j = 0; j < n; j++){
		while (!s2.empty()){
			int i = s2.begin()->second;
			if (r[i] < j){
				s1.erase(make_pair(i, r[i]));
				s2.erase(make_pair(r[i], i));
			} else {
				break;
			}
		}

		assert(s1.size() == s2.size());

		auto it = s1.end();
		while (true){
			if (it == s1.begin()) break;
			it--;

			int i = it->first;
			if (i < l[j]) break;

			if (i + 1 < j) ans.emplace_back(i + 1, j - 1);
		}

		s1.emplace(j, r[j]);
		s2.emplace(r[j], j);
	}

	return ans;
}

const int MaxN = 2500;

vector<pair<int, int>> per_col[MaxN][MaxN];
vector<pair<int, int>> per_row[MaxN][MaxN];

vector<tuple<int, int, int>> opening[MaxN];
vector<pair<int, int>> vals_to_add[MaxN];

int fen[MaxN + 1][MaxN + 1];

inline void add(int _x, int _y, int val){
	_x++, _y++;
	int x = _x;
	while (x <= MaxN){
		int y = _y;
		while (y <= MaxN){
			fen[x][y] += val;
			y += (-y & y);
		}
		x += (-x & x);
	}
}

inline int get(int _x, int _y){
	_x++, _y++;
	int res = 0;
	int x = _x;
	while (x > 0){
		int y = _y;
		while (y > 0){
			res += fen[x][y];
			y -= (-y & y);
		}
		x -= (-x & x);
	}
	return res;
}

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

	for (int i = 1; i + 1 < n; i++){
		vector<pair<int, int>> f = find_borders(A[i]);

		for (auto [l, r] : f){
			auto &v = per_col[l][r];
			if (v.empty() || v.back().second != i - 1){
				v.emplace_back(i, i);
			} else {
				v.back().second++;
			}
		}
	}

	for (int j = 1; j + 1 < m; j++){
		vector<int> col(n);
		for (int i = 0; i < n; i++) col[i] = A[i][j];
		vector<pair<int, int>> f = find_borders(col);
		for (auto [x, y] : f){
			auto &v = per_row[x][y];
			if (v.empty() || v.back().second != j - 1){
				v.emplace_back(j, j);
			} else {
				v.back().second++;
			}
		}
	}

	for (int x = 0; x < n; x++){
		for (int y = x; y < n; y++){
			for (auto [l, r] : per_row[x][y]){
				opening[l].emplace_back(r, x, y);
			}
		}
	}

	long long ans = 0;
	for (int l = 1; l < m - 1; l++){
		for (auto [r, x, y] : opening[l]){
			vals_to_add[r].emplace_back(x, y);
		}

 		for (int r = m - 2; r >= l; r--){
			for (auto [x, y] : vals_to_add[r]){
				x = n - x - 1;
				add(x, y, 1);
			}

			for (auto [X, Y] : per_col[l][r]){
				X = n - X - 1;
				ans += get(X, Y);
			}

		}

		for (int r = l; r <= m - 2; r++){
			for (auto [x, y] : vals_to_add[r]){
				x = n - x - 1;
				add(x, y, -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