Submission #830607

#	Time	Username	Problem	Language	Result	Execution time	Memory
830607		pavement	Rectangles (IOI19_rect)	C++17	100 / 100	3188 ms	605964 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define mp make_pair
#define pb push_back
#define eb emplace_back

using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ll = long long;

ll count_rectangles(vector<vector<int> > a) {
	ll ans = 0;
	int n = (int)a.size(), m = (int)a[0].size();
	vector<vector<vector<ii> > > horiz(n, vector<vector<ii> >(m)), vert(n, vector<vector<ii> >(m));
	for (int i = 1; i + 1 < n; i++) {
		vector<int> st_max;
		for (int j = 0; j < m; j++) {
			while (!st_max.empty() && a[i][st_max.back()] <= a[i][j]) {				
				if (j - 1 > 0 && st_max.back() + 1 <= j - 1 && st_max.back() + 2 < m) {
					horiz[i][j - 1].eb(st_max.back() + 1, 1);
				}
				st_max.pop_back();
			}
			st_max.pb(j);
		}
	}
	for (int i = 1; i + 1 < n; i++) {
		vector<int> st_max;
		for (int j = m - 1; j >= 0; j--) {
			while (!st_max.empty() && a[i][st_max.back()] <= a[i][j]) {				
				if (st_max.back() < m && j + 1 <= st_max.back() - 1 && j + 1 > 0) {
					horiz[i][st_max.back() - 1].eb(j + 1, 1);
				}
				st_max.pop_back();
			}
			st_max.pb(j);
		}
	}
	for (int i = 1; i + 1 < m; i++) {
		vector<int> st_max;
		for (int j = 0; j < n; j++) {
			while (!st_max.empty() && a[st_max.back()][i] <= a[j][i]) {				
				if (j - 1 > 0 && st_max.back() + 1 <= j - 1 && st_max.back() + 2 < n) {
					vert[j - 1][i].eb(st_max.back() + 1, 1);
				}
				st_max.pop_back();
			}
			st_max.pb(j);
		}
	}
	for (int i = 1; i + 1 < m; i++) {
		vector<int> st_max;
		for (int j = n - 1; j >= 0; j--) {
			while (!st_max.empty() && a[st_max.back()][i] <= a[j][i]) {				
				if (st_max.back() < n && j + 1 <= st_max.back() - 1 && j + 1 > 0) {
					vert[st_max.back() - 1][i].eb(j + 1, 1);
				}
				st_max.pop_back();
			}
			st_max.pb(j);
		}
	}
	for (int i = 1; i + 1 < n; i++) {
		for (int j = 1; j + 1 < m; j++) {
			sort(horiz[i][j].begin(), horiz[i][j].end());
			horiz[i][j].erase(unique(horiz[i][j].begin(), horiz[i][j].end()), horiz[i][j].end());
			sort(vert[i][j].begin(), vert[i][j].end());
			vert[i][j].erase(unique(vert[i][j].begin(), vert[i][j].end()), vert[i][j].end());
			for (auto &[k, l] : horiz[i][j]) {
				auto it = lower_bound(horiz[i - 1][j].begin(), horiz[i - 1][j].end(), mp(k, 0));
				if (it != horiz[i - 1][j].end() && it->first == k) {
					l = it->second + 1;
				}
				//~ cout << "H " << i << ' ' << j << ' ' << k << ' ' << l << '\n';
			}
			for (auto &[k, l] : vert[i][j]) {
				auto it = lower_bound(vert[i][j - 1].begin(), vert[i][j - 1].end(), mp(k, 0));
				if (it != vert[i][j - 1].end() && it->first == k) {
					l = it->second + 1;
				}
				//~ cout << "V " << i << ' ' << j << ' ' << k << ' ' << l << '\n';
			}
			vector<iii> events;
			for (auto [k1, l1] : horiz[i][j]) {
				events.eb(j - k1 + 1, 0, l1);
			}
			for (auto [k2, l2] : vert[i][j]) {
				events.eb(l2, 1, i - k2 + 1);
			}
			sort(events.begin(), events.end());
			tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ss;
			int idx = 0;
			for (auto [_, type, x] : events) {
				if (type == 0) {
					ss.insert(mp(x, idx++));
				} else {
					ans += (int)ss.size() - ss.order_of_key(mp(x, -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