Submission #779185

#	Time	Username	Problem	Language	Result	Execution time	Memory
779185		ieeqwq	Rectangles (IOI19_rect)	C++17	100 / 100	3561 ms	947648 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "rect.h"
using namespace std;
using LL = long long;
struct fenwick {
	int n;
	vector<int> t;
	fenwick(int _n) : n(_n), t(_n) {
	}
	void modify(int x, int v) {
		for (int i = x + 1; i; i -= i & -i) {
			t[i - 1] += v;
		}
	}
	int get(int x) {
		int r = 0;
		for (int i = x + 1; i <= n; i += i & -i) {
			r += t[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;
		static fenwick tr(2500);
		for (auto [x, y] : q) {
			while (idx < p.size() && p[idx][0] <= x) {
				tr.modify(p[idx++][1], 1);
			}
			res += tr.get(y);
		}
		while (idx) {
			tr.modify(p[--idx][1], -1);
		}
		return res;
	}
};
LL count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	vector<vector<array<int, 2>>> avc(n), avr(m);
	for (int r = 0; r < n; r++) {
		vector<int> lef(m), rgt(m);
		{
			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]});
			}
		}
		sort(avc[r].begin(), avc[r].end()), avc[r].erase(unique(avc[r].begin(), avc[r].end()), avc[r].end());
	}
	for (int c = 0; c < m; c++) {
		vector<int> lef(n), rgt(n);
		{
			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]});
			}
		}
		sort(avr[c].begin(), avr[c].end()), avr[c].erase(unique(avr[c].begin(), avr[c].end()), avr[c].end());
	}
	vector<vector<int>> down(n), right(m);
	for (int i = n - 2; i >= 1; i--) {
		down[i].resize(avc[i].size());
		for (int j = 0; j < avc[i].size(); j++) {
			auto it = avc[i][j];
			int where = lower_bound(avc[i + 1].begin(), avc[i + 1].end(), it) - avc[i + 1].begin();
			if (i == n - 2 || (where == avc[i + 1].size() || avc[i + 1][where] != it)) {
				down[i][j] = i;
			} else {
				down[i][j] = down[i + 1][where];
			}
		}
	}
	for (int i = m - 2; i >= 1; i--) {
		right[i].resize(avr[i].size());
		for (int j = 0; j < avr[i].size(); j++) {
			auto it = avr[i][j];
			int where = lower_bound(avr[i + 1].begin(), avr[i + 1].end(), it) - avr[i + 1].begin();
			if (i == m - 2 || (where == avr[i + 1].size() || avr[i + 1][where] != it)) {
				right[i][j] = i;
			} else {
				right[i][j] = right[i + 1][where];
			}
		}
	}
	vector d(n, vector<DS>(m));
	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, right[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 = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ans += d[i][j].solve();
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In member function 'int DS::solve()':
rect.cpp:39: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]
   39 |    while (idx < p.size() && p[idx][0] <= x) {
      |           ~~~~^~~~~~~~~~
rect.cpp: In function 'LL count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:130: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]
  130 |   for (int j = 0; j < avc[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:133:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |    if (i == n - 2 || (where == avc[i + 1].size() || avc[i + 1][where] != it)) {
      |                       ~~~~~~^~~~~~~~~~~~~~~~~~~~
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].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
rect.cpp:145:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    if (i == m - 2 || (where == avr[i + 1].size() || avr[i + 1][where] != it)) {
      |                       ~~~~~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:154: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]
  154 |   for (int i = 0; i < avr[c].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
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 < 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