Submission #1069635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069635		Gromp15	Rectangles (IOI19_rect)	C++17	59 / 100	2966 ms	1048576 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

using namespace std;

const int nax = 2505;
short u[nax][nax], d[nax][nax], l[nax][nax], r[nax][nax], st[nax];
vector<short> who[nax][nax], who2[nax][nax];
vector<bool> vis[nax][nax], vis2[nax][nax];

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	for (int i = 0, tp = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			while (tp && a[i][j] >= a[i][st[tp]]) tp--;
			l[i][j] = tp ? st[tp] : m + 1;
			st[++tp] = j;
		}
		tp = 0;
		for (int j = m-1; j >= 0; j--) {
			while (tp && a[i][j] >= a[i][st[tp]]) tp--;
			r[i][j] = tp ? st[tp] : -2;
			st[++tp] = j;
		}
	}
	for (int i = 0, tp = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			while (tp && a[j][i] >= a[st[tp]][i]) tp--;
			u[j][i] = tp ? st[tp] : n + 1;
			st[++tp] = j;
		}
		tp = 0;
		for (int j = n-1; j >= 0; j--) {
			while (tp && a[j][i] >= a[st[tp]][i]) tp--;
			d[j][i] = tp ? st[tp] : -2;
			st[++tp] = j;
		}
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { 
		int L = l[i][j] + 1, R = r[i][j] - 1;
		if (L <= R) who[i][L].emplace_back(R);
		int U = u[i][j] + 1, D = d[i][j] - 1;
		if (U <= D) who2[U][j].emplace_back(D);
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		sort(all(who[i][j]));
		sort(all(who2[i][j]));
		who[i][j].erase(unique(all(who[i][j])), who[i][j].end());
		who2[i][j].erase(unique(all(who2[i][j])), who2[i][j].end());
		vis[i][j].resize(sz(who[i][j]));
		vis2[i][j].resize(sz(who2[i][j]));
	}
	vector<vector<ar<short, 3>>> add(n), rem(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < sz(who[i][j]); k++) if (!vis[i][j][k]) {
				int r = who[i][j][k];
				int d = i;
				while (d+1 < n) {
					auto it = lower_bound(all(who[d+1][j]), r);
					if (it != who[d+1][j].end() && *it == r) d++, vis[d][j][it - who[d][j].begin()] = 1;
					else break;
				}
				add[i].push_back({d, j, r});
				if (d+1 < n) rem[d+1].push_back({d, j, r});
			}
		}
	}
	set<ar<short, 3>> got;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		for (auto [d, l, r] : add[i]) {
			assert(!got.count({d, l, r}));
			got.insert({d, l, r});
		}
		for (auto [d, l, r] : rem[i]) {
			assert(got.count({d, l, r}));
			got.erase({d, l, r});
		}
		vector<ar<short, 3>> cur;
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < sz(who2[i][j]); k++) if (!vis2[i][j][k]) {
				int d = who2[i][j][k], r = j;
				while (r+1 < m) {
					auto it = lower_bound(all(who2[i][r+1]), d);
					if (it != who2[i][r+1].end() && *it == d) r++, vis2[i][r][it - who2[i][r].begin()] = 1;
					else break;
				}
				cur.push_back({d, j, r});
			}
		}
		for (auto [d, l, r] : cur) for (auto [d2, l2, r2] : got) ans += d2 >= d && l2 >= l && r2 <= r;
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:73:23: warning: narrowing conversion of 'd' from 'int' to 'short int' [-Wnarrowing]
   73 |     add[i].push_back({d, j, r});
      |                       ^
rect.cpp:73:26: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   73 |     add[i].push_back({d, j, r});
      |                          ^
rect.cpp:73:29: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   73 |     add[i].push_back({d, j, r});
      |                             ^
rect.cpp:74:38: warning: narrowing conversion of 'd' from 'int' to 'short int' [-Wnarrowing]
   74 |     if (d+1 < n) rem[d+1].push_back({d, j, r});
      |                                      ^
rect.cpp:74:41: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   74 |     if (d+1 < n) rem[d+1].push_back({d, j, r});
      |                                         ^
rect.cpp:74:44: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   74 |     if (d+1 < n) rem[d+1].push_back({d, j, r});
      |                                            ^
rect.cpp:98:20: warning: narrowing conversion of 'd' from 'int' to 'short int' [-Wnarrowing]
   98 |     cur.push_back({d, j, r});
      |                    ^
rect.cpp:98:23: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
   98 |     cur.push_back({d, j, r});
      |                       ^
rect.cpp:98:26: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   98 |     cur.push_back({d, j, r});
      |                          ^

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28