Submission #143810

#	Time	Username	Problem	Language	Result	Execution time	Memory
143810		ainta	Rectangles (IOI19_rect)	C++17	100 / 100	3590 ms	803572 KiB

rect

#include "rect.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

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

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

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

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

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

int BIT[2600];

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(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	int i, j;
	for (i = 0; i < n; i++)for (j = 0; j < m; j++)w[i + 1][j + 1] = a[i][j];

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			T[j] = w[i][j];
		}
		PreCalc(m);
		for (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 (i = 1; i <= m; i++) {
		for (j = 1; j <= n; j++) {
			T[j] = w[j][i];
		}
		PreCalc(n);
		for (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 (i = n; i >= 1; i--) {
		for (j = 1; j <= n; j++)lastH[j] = CH[j] = 0;
		for (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