Submission #843627

#	Time	Username	Problem	Language	Result	Execution time	Memory
843627		siewjh	Rectangles (IOI19_rect)	C++17	100 / 100	2909 ms	1004852 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2505;
int rows, cols;
ll fw[MAXN];
vector<int> prs[MAXN][MAXN];
vector<pair<int, int>> lrc[MAXN][MAXN], tbc[MAXN][MAXN];

void update(int x, ll v){
	while (x < cols){
		fw[x] += v;
		x += (x & (-x));
	}
}

void rupdate(int x, int y, ll v){
	update(x, v); update(y + 1, -v);
}

ll query(int x){
	ll ans = 0;
	while (x){
		ans += fw[x];
		x -= (x & (-x));
	}
	return ans;
}

ll count_rectangles(vector<vector<int>> a) {
	rows = a.size(), cols = a[0].size();
	for (int i = 0; i < rows; i++){
		stack<int> s;
		for (int j = 0; j < cols; j++){
			while (!s.empty() && a[i][j] > a[i][s.top()]) s.pop();
			if (!s.empty() && s.top() + 1 != j) prs[s.top()][j].push_back(i);
			s.push(j);
		}
		while (!s.empty()) s.pop();
		for (int j = cols - 1; j >= 0; j--){
			bool same = false;
			while (!s.empty() && a[i][j] >= a[i][s.top()]){
				if (a[i][j] == a[i][s.top()]) same = true;
				s.pop();
			}
			if (!same && !s.empty() && s.top() - 1 != j) prs[j][s.top()].push_back(i);
			s.push(j);
		}
	}
	for (int i = 0; i < cols; i++)
		for (int j = i + 2; j < cols; j++){
			int sz = prs[i][j].size();
			for (int s = 0; s < sz; s++){
				int e = s;
				while (e != sz - 1 && prs[i][j][e + 1] == prs[i][j][e] + 1) e++;
				for (int k = s; k <= e; k++) lrc[prs[i][j][k]][i + 1].push_back({prs[i][j][e], j - 1});
				s = e;
			}
		}
	for (int j = 0; j < cols; j++){
		stack<int> s;
		for (int i = 0; i < rows; i++){
			while (!s.empty() && a[i][j] > a[s.top()][j]) s.pop();
			if (!s.empty() && s.top() + 1 != i) prs[i][s.top()].push_back(j);
			s.push(i);
		}
		for (int i = rows - 1; i >= 0; i--){
			bool same = 0;
			while (!s.empty() && a[i][j] >= a[s.top()][j]){
				if (a[i][j] == a[s.top()][j]) same = 1;
				s.pop();
			}
			if (!same && !s.empty() && s.top() - 1 != i) prs[s.top()][i].push_back(j);
			s.push(i);
		}
	}
	for (int i = 0; i < rows; i++)
		for (int j = i + 2; j < rows; j++){
			int sz = prs[j][i].size();
			for (int s = 0; s < sz; s++){
				int e = s;
				while (e != sz - 1 && prs[j][i][e + 1] == prs[j][i][e] + 1) e++;
				for (int k = s; k <= e; k++) tbc[i + 1][prs[j][i][k]].push_back({j - 1, prs[j][i][e]});
				s = e;
			}
		}
	ll ans = 0;
	for (int i = 1; i < rows - 1; i++)
		for (int j = 1; j < cols - 1; j++){
			sort(lrc[i][j].begin(), lrc[i][j].end());
			sort(tbc[i][j].begin(), tbc[i][j].end());
			int ind = 0;
			for (auto p : lrc[i][j]){
				int r, c; tie(r, c) = p;
				while (ind != tbc[i][j].size() && tbc[i][j][ind].first <= r){
					rupdate(1, tbc[i][j][ind].second, 1);
					ind++;
				}
				ans += query(c);
			}
			for (int k = 0; k < ind; k++) rupdate(1, tbc[i][j][k].second, -1);
		}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     while (ind != tbc[i][j].size() && tbc[i][j][ind].first <= r){
      |            ~~~~^~~~~~~~~~~~~~~~~~~

• 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