Submission #223000

#	Time	Username	Problem	Language	Result	Execution time	Memory
223000		abeker	Rectangles (IOI19_rect)	C++17	72 / 100	5102 ms	1004328 KiB

rect

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

typedef long long ll;
typedef pair <short, short> pii;

const int MAXN = 2.5e3 + 5;

class Fenwick {
	int n;
	int f[MAXN];
	public:
		Fenwick(int _n) {
			n = _n;
			for (int i = 0; i <= n; i++)
				f[i] = 0;
		}
		Fenwick(){}
		void update(int x, int val) {
			for (x++; x <= n; x += x & -x)
				f[x] += val;
		}
		int get(int x) {
			int res = 0;
			for (x++; x; x -= x & -x)
				res += f[x];
			return res;
		}
		int query(int l, int r) {
			return get(r) - get(l - 1);
		}
};

short foo[MAXN];
vector <short> rows[MAXN][MAXN], cols[MAXN][MAXN];
vector <pii> in[MAXN][MAXN], out[MAXN][MAXN];
Fenwick loga[MAXN];

void find_pairs(const vector <int> &arr, vector <short> ref[MAXN][MAXN], int idx) {
	int n = arr.size(), sz = 0;
	for (int i = 0; i < n; i++) {
		while (sz && arr[foo[sz - 1]] < arr[i])
			sz--;
		if (sz && foo[sz - 1] < i - 1)
			ref[foo[sz - 1]][i].push_back(idx);
		foo[sz++] = i;
	}
	sz = 0;
	for (int i = n - 1; i >= 0; i--) {
		while (sz && arr[foo[sz - 1]] < arr[i])
			sz--;
		if (sz && arr[foo[sz - 1]] > arr[i] && foo[sz - 1] > i + 1)
			ref[i][foo[sz - 1]].push_back(idx);
		foo[sz++] = i;
	}
}

ll count_rectangles(vector <vector <int>> a) {
	int N = a.size();
	int M = a[0].size();
	
	for (int i = 0; i < N; i++) 
		find_pairs(a[i], rows, i);
	
	for (int j = 0; j < M; j++) {
		vector <int> curr;
		for (int i = 0; i < N; i++)
			curr.push_back(a[i][j]);
		find_pairs(curr, cols, j);
	}
	
	for (int i = 0; i < N; i++)
		for (int j = i + 2; j < N; j++) {
			int lst = 0;
			int sz = cols[i][j].size();
			for (int k = 0; k < sz; k++) 
				if (k == sz - 1 || cols[i][j][k + 1] > cols[i][j][k] + 1) {
					int lo = max(cols[i][j][lst] - 1, 0);
					int hi = min(cols[i][j][k] + 1, M - 1);
					for (int l = lo; l <= hi; l++) {
						in[l][lo].push_back({i, j});
						out[l][hi].push_back({i, j});
					}
					lst = k + 1;
				}	
		}
	
	ll sol = 0;
	for (int i = 0; i < N; i++)
		loga[i] = Fenwick(N);
	for (int i = 0; i < M; i++)
		for (int j = 0; j < M; j++) {
			for (auto it : in[i][j])
				loga[it.first].update(it.second, 1);
			if (j > i + 1) {
				int lst = 0;
				int sz = rows[i][j].size();
				for (int k = 0; k < sz; k++) 
					if (k == sz - 1 || rows[i][j][k + 1] > rows[i][j][k] + 1) {
						int lo = max(rows[i][j][lst] - 1, 0);
						int hi = min(rows[i][j][k] + 1, N - 1);
						for (int l = lo; l <= hi; l++) 
							sol += loga[l].query(lo, hi);
						lst = k + 1;
					}	
			}
			for (auto it : out[i][j])
				loga[it.first].update(it.second, -1);
		}
	
	return sol;
}

• 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