Submission #779224

#	Time	Username	Problem	Language	Result	Execution time	Memory
779224		ieeqwq	Rectangles (IOI19_rect)	C++17	100 / 100	2375 ms	931836 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "rect.h"
using namespace std;
using LL = long long;
int fenwick[2500];
inline void modify(int x, int v) {
	for (int i = x + 1; i; i -= i & -i) {
		fenwick[i - 1] += v;
	}
}
inline int get(int x) {
	int r = 0;
	for (int i = x + 1; i <= 2500; i += i & -i) {
		r += fenwick[i - 1];
	}
	return r;
}
struct DS {
	vector<array<int, 2>> p, q;
	DS() = default;
	void insert(int x, int y) {
		p.push_back({x, y});
	}
	void query(int x, int y) {
		q.push_back({x, y});
	}
	int solve() {
		int res = 0;
		sort(p.begin(), p.end()), sort(q.begin(), q.end());
		int idx = 0;
		for (const auto &[x, y] : q) {
			while (idx < p.size() && p[idx][0] <= x) {
				modify(p[idx++][1], 1);
			}
			res += get(y);
		}
		while (idx) {
			modify(p[--idx][1], -1);
		}
		return res;
	}
} d[2500][2500];
vector<array<int, 2>> avc[2500], avr[2500];
vector<int> down[2500], rght[2500];
int lef[2500], rgt[2500];
int Where[2500][2500];
LL count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	for (int r = 1; r <= n - 2; r++) {
		{
			stack<int> st;
			for (int c = 1; c <= m - 2; c++) {
				while (st.size() && a[r][st.top()] <= a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					lef[c] = 1;
				} else {
					lef[c] = st.top() + 1;
				}
				st.push(c);
			}
		}
		{
			stack<int> st;
			for (int c = m - 2; c >= 1; c--) {
				while (st.size() && a[r][st.top()] < a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					rgt[c] = m - 2;
				} else {
					rgt[c] = st.top() - 1;
				}
				st.push(c);
			}
		}
		for (int i = 1; i <= m - 2; i++) {
			if (a[r][i] < min(a[r][lef[i] - 1], a[r][rgt[i] + 1])) {
				avc[r].push_back({lef[i], rgt[i]});
			}
		}
	}
	for (int c = 1; c <= m - 2; c++) {
		{
			stack<int> st;
			for (int r = 1; r <= n - 2; r++) {
				while (st.size() && a[st.top()][c] <= a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					lef[r] = 1;
				} else {
					lef[r] = st.top() + 1;
				}
				st.push(r);
			}
		}
		{
			stack<int> st;
			for (int r = n - 2; r >= 1; r--) {
				while (st.size() && a[st.top()][c] < a[r][c]) {
					st.pop();
				}
				if (st.empty()) {
					rgt[r] = n - 2;
				} else {
					rgt[r] = st.top() - 1;
				}
				st.push(r);
			}
		}
		for (int i = 1; i <= n - 2; i++) {
			if (a[i][c] < min(a[lef[i] - 1][c], a[rgt[i] + 1][c])) {
				avr[c].push_back({lef[i], rgt[i]});
			}
		}
	}
	memset(Where, -1, sizeof Where);
	for (int i = n - 2; i >= 1; i--) {
		down[i].resize(avc[i].size());
		for (int j = 0; j < avc[i + 1].size(); j++) {
			auto [x, y] = avc[i + 1][j];
			Where[x][y] = j;
		}
		for (int j = 0; j < avc[i].size(); j++) {
			auto it = avc[i][j];
			int where = Where[it[0]][it[1]];
			if (where == -1 || i == n - 2) {
				down[i][j] = i;
			} else {
				down[i][j] = down[i + 1][where];
			}
		}
		for (auto [x, y] : avc[i + 1]) {
			Where[x][y] = -1;
		}
	}
	for (int i = m - 2; i >= 1; i--) {
		rght[i].resize(avr[i].size());
		for (int j = 0; j < avr[i + 1].size(); j++) {
			auto [x, y] = avr[i + 1][j];
			Where[x][y] = j;
		}
		for (int j = 0; j < avr[i].size(); j++) {
			auto it = avr[i][j];
			int where = Where[it[0]][it[1]];
			if (where == -1) {
				rght[i][j] = i;
			} else {
				rght[i][j] = rght[i + 1][where];
			}
		}
		for (auto [x, y] : avr[i + 1]) {
			Where[x][y] = -1;
		}
	}
	for (int c = 1; c <= m - 2; c++) {
		for (int i = 0; i < avr[c].size(); i++) {
			auto [L, R] = avr[c][i];
			d[L][c].insert(R, rght[c][i]);
		}
	}
	for (int r = 1; r <= n - 2; r++) {
		for (int i = 0; i < avc[r].size(); i++) {
			auto [L, R] = avc[r][i];
			d[r][L].query(down[r][i], R);
		}
	}
	LL ans = 0;
	for (int i = 1; i <= n - 2; i++) {
		for (int j = 1; j <= m - 2; j++) {
			ans += d[i][j].solve();
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In member function 'int DS::solve()':
rect.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    while (idx < p.size() && p[idx][0] <= x) {
      |           ~~~~^~~~~~~~~~
rect.cpp: In function 'LL count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for (int j = 0; j < avc[i + 1].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for (int j = 0; j < avc[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for (int j = 0; j < avr[i + 1].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for (int j = 0; j < avr[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:160:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for (int i = 0; i < avr[c].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:166:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   for (int i = 0; i < avc[r].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~

• 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