Submission #1196852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196852		MateiKing80	Rectangles (IOI19_rect)	C++20	100 / 100	1916 ms	803544 KiB

rect

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

using namespace std;

const int N = 2600;

int n, m, w[N][N], T[N];
vector<int>Right[N][N], Down[N][N];

int st[N], RR[N], LL[N];

void PreCalc(int n) {
	int top = 0;
	for (int i = 1; i <= n; i ++)
		RR[i] = LL[i] = 0;
	for (int i = 1; i <= n; i ++) {
		while (top && T[st[top]] <= T[i]) {
			RR[st[top]] = i;
			top --;
		}
		st[++ top] = i;
	}
	top = 0;
	for (int i = n; i >= 1; i --) {
		while (top && T[st[top]] <= T[i]) {
			LL[st[top]] = i;
			top--;
		}
		st[++top] = i;
	}
}

int last[N][N], CC[N][N];
int lastH[N], CH[N];

struct point {
	int x, y, ck;
	bool operator < (const point &p) const {
		return x < p.x;
	}
} U[10100];

int BIT[N];

void Add(int a, int b) {
	while (a <= m) {
		BIT[a] += b;
		a += a & -a;
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= a & -a;
	}
	return r;
}

long long count_rectangles(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < m; j ++)
			w[i + 1][j + 1] = a[i][j];

	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++)
			T[j] = w[i][j];
		PreCalc(m);
		for (int j = 1; j <= m; j ++) {
			if (RR[j] && RR[j] > j + 1)
				Right[i][j + 1].push_back(RR[j] - 1);
			if (LL[j] && LL[j] < j - 1 && RR[LL[j]] != j)
				Right[i][LL[j] + 1].push_back(j - 1);
		}
	}
	for (int i = 1; i <= m; i ++) {
		for (int j = 1; j <= n; j ++)
			T[j] = w[j][i];
		PreCalc(n);
		for (int j = 1; j <= n; j ++) {
			if (RR[j] && RR[j] > j + 1)
				Down[j + 1][i].push_back(RR[j] - 1);
			if (LL[j] && LL[j] < j - 1 && RR[LL[j]] != j)
				Down[LL[j] + 1][i].push_back(j - 1);
		}
	}
	long long res = 0;
	for (int i = n; i >= 1; i --) {
		for (int j = 1; j <= n; j ++)
			lastH[j] = CH[j] = 0;
		for (int j = m; j >= 1; j--) {
			for (auto &t : Right[i][j]) {
				if (last[j][t] != i + 1)
					CC[j][t] = 0;
				CC[j][t] ++;
				last[j][t] = i;
			}
			for (auto &t : Down[i][j]) {
				if (lastH[t] != j + 1)
					CH[t] = 0;
				CH[t] ++;
				lastH[t] = j;
			}
			int cnt = 0;
			for (auto &t : Right[i][j]) {
				U[cnt ++] = {i, t, 1};
				U[cnt ++] = {i + CC[j][t], t, -1};
			}
			sort(U, U + cnt);
			sort(Down[i][j].begin(), Down[i][j].end());
			int pv = 0;
			for (auto &t : Down[i][j]) {
				while (pv < cnt && U[pv].x <= t) {
					Add(U[pv].y, U[pv].ck);
					pv ++;
				}
				res += Sum(j + CH[t] - 1);
			}
			while (pv < cnt) {
				Add(U[pv].y, U[pv].ck);
				pv ++;
			}
		}
	}
	return res;
}

• 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