Submission #1103886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103886		_8_8_	Rectangles (IOI19_rect)	C++17	0 / 100	3053 ms	480520 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2500 + 12;
int n, m, a[N][N], it[N][N];
vector<array<int, 2>> r[N];
vector<int> id[N][N], t[N][N], f[N][N];
int c[N][N];
void upd(int x, int y, int val) {
	c[x][y] += val;
	// while(x <= m) {
	// 	int j = y;
	// 	while(j <= m) {
	// 		c[x][j] += val;
	// 		j += j & -j;
	// 	}
	// 	x += x & -x;	
	// }
}
int get(int x, int y) {
	// for()
	int ret = 0;
	while(x) {
		int j = y;
		while(j) {
			ret += c[x][j];
			j -= j & -j;
		}
		x -= x & -x;
	}
	return ret;
}
int get(int x, int y, int x1, int y1) {
	int ret = 0;
	for(int i = x; i <= x1; i++) {
		for(int j = y; j <= y1; j++) {
			ret += c[i][j];
		}
	}
	return ret;
	return get(x1, y1) - get(x - 1, y1) - get(x1, y - 1) + get(x - 1, y - 1);
}
void prec() {
	for(int i = 2; i < n; i++) {
		vector<int> st;
		for(int j = 1; j <= m; j++) {
			while(!st.empty() && a[i][st.back()] < a[i][j]) {
				st.pop_back();
			} 
			if(!st.empty()) {
				int l = st.back();
				if(l + 1 <= j - 1) {
					r[i].push_back({l + 1, j - 1});
				}
			}
			st.push_back(j);
		}
		st.clear();
		for(int j = m; j >= 1; j--) {
			while(!st.empty() && a[i][st.back()] < a[i][j]) {
				st.pop_back();
			}
			if(!st.empty()) {
				int l = st.back();
				if(j + 1 <= l - 1) {
					r[i].push_back({j + 1, l - 1});
				}
			}
			st.push_back(j);
		}
		sort(r[i].begin(), r[i].end());
		r[i].resize(unique(r[i].begin(), r[i].end()) - r[i].begin());
		for(auto [l, r]:r[i]) {
			id[l][r].push_back(i);
		}
	}
	for(int j = 2; j < m; j++) {
		vector<int> st;
		for(int i = 1; i <= n; i++) {
			while(!st.empty() && a[st.back()][j] < a[i][j]) {
				st.pop_back();
			}
			if(!st.empty()) {
				int l = st.back();
				if(l + 1 <= i - 1) {
					t[l + 1][j].push_back(i - 1);
				}
			}
			st.push_back(i);
		}
		st.clear();
		for(int i = n; i >= 1; i--) {
			while(!st.empty() && a[st.back()][j] < a[i][j]) {
				st.pop_back();
			}
			if(!st.empty()) {
				int l = st.back();
				if(l - 1 >= i + 1) {
					t[i + 1][j].push_back(l - 1);
				}
			}
			st.push_back(i);
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			sort(t[i][j].begin(), t[i][j].end());
			t[i][j].resize(unique(t[i][j].begin(), t[i][j].end()) - t[i][j].begin());
		}
	}
	for(int i = 1; i <= m; i++) {
		for(int j = i; j <= m; j++) {
			f[i][j].resize((int)id[i][j].size());
			for(int k = 0; k < (int)f[i][j].size(); k++) {
				if(k && id[i][j][k] - 1 == id[i][j][k - 1]) {
					f[i][j][k] = f[i][j][k - 1];
				} else {
					int it = k + 1;
					while(it < (int)id[i][j].size() && id[i][j][it] - 1 == id[i][j][it - 1]) {
						it++;
					}
					it--;
					f[i][j][k] = id[i][j][it];
				}
			}
		}
	}
}
ll solve() {
	ll res = 0;
	for(int i = 2; i < n; i++) {
		vector<array<int, 2>> pt;
		for(int j = 2; j < m; j++) {
			for(int f:t[i][j]) {
				pt.push_back({f, j});
			}
		}
		sort(pt.begin(), pt.end());
		vector<array<int, 3>> s;
		for(int i = 0; i < (int)pt.size(); ) {
			int j = i + 1;
			while(j < (int)pt.size() && pt[j][0] == pt[j - 1][0] && pt[j][1] == pt[j - 1][1] + 1) {
				j++;
			}
			assert(pt[i][1] >= 1 && pt[j - 1][1] <= m);
			s.push_back({pt[i][0], pt[i][1], pt[j - 1][1]});
			i = j;
		}
		sort(s.begin(), s.end());
		sort(r[i].begin(), r[i].end(), [&](array<int, 2> x, array<int, 2> y){
			return f[x[0]][x[1]][it[x[0]][x[1]]] < f[y[0]][y[1]][it[y[0]][y[1]]];
		});
		int ti = 0;
		for(auto [l, r]:r[i]) {
			while(ti < (int)s.size() && s[ti][0] <= f[l][r][it[l][r]]) {
				upd(s[ti][1], s[ti][2], 1);
				ti++;
			}
			res += get(1, l, r, m);
			// for(int j = 0; j < ti; j++) {
			// 	if(s[j][1] <= l && s[j][2] >= r) {
			// 		res++;
			// 	}
			// }
		}
		memset(c, 0, sizeof(c));
		// for(int j = 0; j < ti; j++) {
		// 	upd(s[j][1], s[j][2], -1);
		// }
		for(auto [l, r]:r[i]) {
			it[l][r]++;
		}
	}
	return res;
}
ll count_rectangles(vector<vector<int> > _A) {
	n = (int)_A.size();
	m = (int)_A[0].size();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			a[i][j] = _A[i - 1][j - 1];
		}
	}
	prec();
	return solve();
}

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