Submission #1107905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107905		Sharky	Rectangles (IOI19_rect)	C++17	72 / 100	1769 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
using ll = long long;

vector<array<int, 2>> ed[2510]; 
vector<pair<int, int>> qr[2510];
ll fen[2510];

void upd(int u, int k) { 
	for (; u <= 2500; u += (u & -u)) fen[u] += (ll) k;
}

ll query(int u) {
	ll res = 0;
	for (; u; u -= (u & -u)) res += fen[u];
	return res;
}

ll count_rectangles(std::vector<std::vector<int32_t>> inp) {
	int n = inp.size(), m = inp[0].size();
	ll ans = 0;
	vector<vector<int>> a(n+1, vector<int> (m+1));
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = inp[i-1][j-1];
	vector<vector<vector<int>>> h(m+1, vector<vector<int>> (m+1));
	vector<vector<vector<int>>> v(n+1, vector<vector<int>> (n+1));
	for (int i = 1; i <= n; i++) {
		stack<int> st;
		for (int j = 1; j <= m; j++) {
			bool eq = 0;
			while (!st.empty() && a[i][st.top()] <= a[i][j]) {
				if (st.top() + 1 < j && !eq) h[st.top() + 1][j - 1].push_back(i);
				if (a[i][st.top()] == a[i][j]) eq = true;
				st.pop();
			}
			if (!st.empty() && st.top() + 1 < j && !eq) h[st.top() + 1][j - 1].push_back(i);
			st.push(j);
		}
	}
	for (int j = 1; j <= m; j++) {
		stack<int> st;
		for (int i = 1; i <= n; i++) {
			bool eq = 0;
			while (!st.empty() && a[st.top()][j] <= a[i][j]) {
				if (st.top() + 1 < i && !eq) v[st.top() + 1][i - 1].push_back(j);
				if (a[st.top()][j] == a[i][j]) eq = true;
				st.pop();
			}
			if (!st.empty() && st.top() + 1 < i && !eq) v[st.top() + 1][i - 1].push_back(j);
			st.push(i);
		}
	}
	vector<vector<vector<array<int, 3>>>> rrect(n+1, vector<vector<array<int, 3>>> (m+1));
	vector<vector<vector<array<int, 3>>>> crect(n+1, vector<vector<array<int, 3>>> (m+1));
	for (int c1 = 1; c1 <= m; c1++) {
		for (int c2 = c1; c2 <= m; c2++) {
			vector<pair<int, int>> pr;
			for (int& row : h[c1][c2]) {
				// printf("strip: row = %d, columns = %d, %d\n", row, c1, c2);
				if (pr.empty() || pr.back().second + 1 != row) pr.push_back({row, row});
				else pr.back().second++;
			}
			for (auto& [lb, rb] : pr) for (int i = lb; i <= rb; i++) crect[i][c1].push_back({c2, i, rb});
		}
	}
	for (int r1 = 1; r1 <= n; r1++) {
		for (int r2 = r1; r2 <= n; r2++) {
			vector<pair<int, int>> pr;
			for (int& col : v[r1][r2]) {
				// printf("strip: column = %d, rows = %d, %d\n", col, r1, r2);
				if (pr.empty() || pr.back().second + 1 != col) pr.push_back({col, col});
				else pr.back().second++;
			}
			for (auto& [lb, rb] : pr) for (int i = lb; i <= rb; i++) rrect[r1][i].push_back({r2, i, rb});
		}
	}
	for (int r1 = 1; r1 <= n; r1++) {
		for (int c1 = 1; c1 <= m; c1++) {
			vector<int> crit;
			for (auto& [r2, lb, rb] : rrect[r1][c1]) {
				crit.push_back(r2);
				qr[r2].push_back({lb, rb});
			}
			for (auto& [c2, lb, rb] : crect[r1][c1]) {
				crit.push_back(lb);
				crit.push_back(rb + 1);
				ed[lb].push_back({1, c2});
				ed[rb + 1].push_back({0, c2});
			}
			sort(crit.begin(), crit.end());
			crit.erase(unique(crit.begin(), crit.end()), crit.end());
			for (auto& ti : crit) {
				for (auto& [x, y] : ed[ti]) {
					if (x) upd(y, 1);
					else upd(y, -1);
				} 
				for (auto& [x, y] : qr[ti]) ans += query(y) - query(x-1);
				// cout << r1 << " " << c1 << " " << ans << '\n';
				ed[ti].clear();
				qr[ti].clear();
			}
 		}
	}
	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: 0 / 28