Submission #1229558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229558		AmirAli_H1	Rectangles (IOI19_rect)	C++17	72 / 100	1360 ms	1053956 KiB

rect

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2500 + 4;

int n, m;
int A[maxn][maxn], L[maxn], R[maxn];
vector<int> A1[maxn][maxn], A2[maxn][maxn];
vector<int> val1[maxn][maxn], val2[maxn][maxn];
vector<pii> lsx; int t[maxn];

void addx(int i, int x) {
	for (++i; i < maxn; i += (i & -i)) t[i] += x;
}

int getx(int i) {
	int res = 0;
	for (++i; i > 0; i -= (i & -i)) res += t[i];
	return res;
}

int G1(int i, int j, int x) {
	if (i < 0 || i >= n || j < 0 || j >= m) return -1;
	int R = lower_bound(all(A1[i][j]), x) - A1[i][j].begin();
	if (R < len(A1[i][j]) && A1[i][j][R] == x) return R;
	else return -1;
}

int G2(int i, int j, int x) {
	if (i < 0 || i >= n || j < 0 || j >= m) return -1;
	int R = lower_bound(all(A2[i][j]), x) - A2[i][j].begin();
	if (R < len(A2[i][j]) && A2[i][j][R] == x) return R;
	else return -1;
}

ll count_rectangles(vector<vector<int>> a) {
	n = len(a); m = len(a[0]);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) A[i][j] = a[i][j];
	}
	if (n < 3 || m < 3) return 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (L[j] = j - 1; L[j] != -1 && A[i][j] > A[i][L[j]]; L[j] = L[L[j]]);
			if (L[j] != -1 && (j - L[j]) >= 2) A1[i][L[j]].pb(j);
		}
		for (int j = m - 1; j >= 0; j--) {
			for (R[j] = j + 1; R[j] != m && A[i][j] > A[i][R[j]]; R[j] = R[R[j]]);
			if (R[j] != m && (R[j] - j) >= 2 && A[i][j] != A[i][R[j]]) A1[i][j].pb(R[j]);
		}
	}
	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			for (L[i] = i - 1; L[i] != -1 && A[i][j] > A[L[i]][j]; L[i] = L[L[i]]);
			if (L[i] != -1 && (i - L[i]) >= 2) A2[L[i]][j].pb(i);
		}
		for (int i = n - 1; i >= 0; i--) {
			for (R[i] = i + 1; R[i] != n && A[i][j] > A[R[i]][j]; R[i] = R[R[i]]);
			if (R[i] != n && (R[i] - i) >= 2 && A[i][j] != A[R[i]][j]) A2[i][j].pb(R[i]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			sort(all(A1[i][j])); sort(all(A2[i][j]));
			val1[i][j].resize(len(A1[i][j])); val2[i][j].resize(len(A2[i][j]));
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < m; j++) {
			for (int R = 0; R < len(A1[i][j]); R++) {
				int x = G1(i + 1, j, A1[i][j][R]);
				if (x != -1) val1[i][j][R] = val1[i + 1][j][x];
				else val1[i][j][R] = i;
			}
		}
	}
	for (int j = m - 1; j >= 0; j--) {
		for (int i = 0; i < n; i++) {
			for (int R = 0; R < len(A2[i][j]); R++) {
				int x = G2(i, j + 1, A2[i][j][R]);
				if (x != -1) val2[i][j][R] = val2[i][j + 1][x];
				else val2[i][j][R] = j;
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			lsx.clear();
			for (int R2 = 0; R2 < len(A2[i - 1][j]); R2++) {
				lsx.pb(Mp(val2[i - 1][j][R2], A2[i - 1][j][R2] - 1));
			}
			sort(all(lsx));
			int R2 = len(lsx) - 1;
			for (int R1 = len(A1[i][j - 1]) - 1; R1 >= 0; R1--) {
				while (R2 >= 0 && lsx[R2].F >= A1[i][j - 1][R1] - 1) {
					addx(lsx[R2].S, 1); R2--;
				}
				ans += getx(val1[i][j - 1][R1]);
			}
			while (R2 + 1 < len(lsx)) {
				addx(lsx[R2 + 1].S, -1); R2++;
			}
		}
	}
	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