Submission #144003

#	Time	Username	Problem	Language	Result	Execution time	Memory
144003		tincamatei	Rectangles (IOI19_rect)	C++14	100 / 100	4712 ms	760004 KiB

rect

#include "rect.h"
#include <cstdio>
#include <algorithm>

using namespace std;

bool goodRect(int i, int j, int exp) {
	return j - i - 1 > 0 && exp >= j - i - 1;
}

struct Column {
	int l1, l2, c;
};

const int MAX_N = 2500;
const int MAX_L = 12;

vector<Column> getColumns(const vector<vector<int> > matr) {
	int N = matr.size(), M = matr[0].size();
	vector<int> stiva(N, 0);
	vector<Column> rez;
	int top;

	for(int c = 0; c < M; ++c) {
		top = 0;
		for(int l = 0; l < N; ++l) {
			bool eq = false;

			while(top > 0 && matr[l][c] >= matr[stiva[top - 1]][c]) {
				if(l - stiva[top - 1] > 1)
					rez.push_back({stiva[top - 1], l, c});
				if(matr[l][c] == matr[stiva[top - 1]][c])
					eq = true;
				--top;
			}

			if(!eq && top > 0 && l - stiva[top - 1] > 1)
				rez.push_back({stiva[top - 1], l, c});
			stiva[top++] = l;
		}
	}

	return rez;
}

bool cmp(Column a, Column b) {
	return a.l1 < b.l1 || (a.l1 == b.l1 && a.l2 < b.l2) || (a.l1 == b.l1 && a.l2 == b.l2 && a.c < b.c);
}

int mylog[1+MAX_N];
int rmqleft[MAX_L][MAX_N][MAX_N];
int rmqright[MAX_L][MAX_N][MAX_N];

void initRmq(const vector<vector<int> > &a) {
	int N = a.size(), M = a[0].size();
	vector<int> stiva(M);
	int top;

	for(int l = 0; l < N; ++l)
		for(int c = 0; c < M; ++c) {
			rmqleft[0][l][c] = 0;
			rmqright[0][l][c] = M - 1;
		}

	for(int l = 0; l < N; ++l) {
		top = 0;
		for(int c = 0; c < M; ++c) {
			bool eq = false;
			while(top > 0 && a[l][c] >= a[l][stiva[top - 1]]) {
				rmqright[0][l][stiva[top - 1]] = c;
				if(a[l][stiva[top - 1]] == a[l][c]) {
					rmqleft[0][l][c] = stiva[top - 1];
					eq = true;
				}
				--top;
			}

			if(!eq && top > 0)
				rmqleft[0][l][c] = stiva[top - 1];
			stiva[top++] = c;
		}
	}

	for(int lg = 1; lg < MAX_L; ++lg)
		for(int l = 0; l < N; ++l)
			for(int c = 0; c < M; ++c) {
				rmqleft[lg][l][c] = max(rmqleft[lg - 1][l][c], rmqleft[lg - 1][l + (1 << (lg - 1))][c]);
				rmqright[lg][l][c] = min(rmqright[lg - 1][l][c], rmqright[lg - 1][l + (1 << (lg - 1))][c]);
			}
	
	for(int i = 2; i <= MAX_N; ++i)
		mylog[i] = mylog[i / 2] + 1;
}

int queryRmq(int c, int l1, int l2, bool left) {
	int lg = mylog[l2 - l1 + 1];
	if(left)
		return max(rmqleft[lg][l1][c], rmqleft[lg][l2 - (1 << lg) + 1][c]);
	else
		return min(rmqright[lg][l1][c], rmqright[lg][l2 - (1 << lg) + 1][c]);
}

int aib[1+MAX_N];

static inline int lsb(int x) {
	return x & (-x);
}

int limInf, limSup;

void update(int poz, int val) {
	poz++;
	while(poz <= limSup) {
		aib[poz] += val;
		poz += lsb(poz);
	}
}

int query(int poz) {
	int rez = 0;
	poz++;
	while(poz > limInf) {
		rez += aib[poz];
		poz -= lsb(poz);
	}
	return rez;
}

enum TypeEvent {
	INSERT,
	ERASE
};

struct Event {
	TypeEvent type;
	int x, c;
};

bool cmpEvent(Event &a, Event &b) {
	return a.x < b.x || (a.x == b.x && a.type < b.type);
}

long long processRectangle(int c1, int c2, int l1, int l2) {
	vector<Event> evs;

	++l1;
	--l2;

	limInf = c1;
	limSup = c2 + 1;

	for(int c = c1; c <= c2; ++c) {
		int left, right;
		right = queryRmq(c, l1, l2, false);

		evs.push_back({INSERT, c, c});
		evs.push_back({ERASE, right, c});
	}
	
	sort(evs.begin(), evs.end(), cmpEvent);

	int lastup = 0;
	long long rez = 0LL;
	for(int c = c1; c <= c2; ++c) {
		while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == INSERT) {
			update(evs[lastup].c, 1);
			++lastup;
		}

		int left = queryRmq(c, l1, l2, true);
		rez = rez + query(max(c - 2, -1)) - query(max(left - 1, -1));

		while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == ERASE) {
			update(evs[lastup].c, -1);
			++lastup;
		}
	}

	while(lastup < evs.size()) {
		if(evs[lastup].type == INSERT)
			update(evs[lastup].c, 1);
		else
			update(evs[lastup].c, -1);
		++lastup;
	}
	return rez;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int N, M;
	long long sum = 0LL;
	N = a.size();
	M = a[0].size();

	initRmq(a);

	vector<Column> rez;
	rez = getColumns(a);
	
	sort(rez.begin(), rez.end(), cmp);

	int i, j;
	i = j = 0;

	while(i < rez.size()) {
		while(j < rez.size() && rez[i].l1 == rez[j].l1 && rez[i].l2 == rez[j].l2 && rez[i].c + (j - i) == rez[j].c)
			++j;
		sum = sum + processRectangle(max(0, rez[i].c - 1), min(M - 1, rez[j - 1].c + 1), rez[i].l1, rez[i].l2);

		i = j;
	}

	return sum;
}

Compilation message (stderr)

rect.cpp: In function 'long long int processRectangle(int, int, int, int)':
rect.cpp:153:7: warning: unused variable 'left' [-Wunused-variable]
   int left, right;
       ^~~~
rect.cpp:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == INSERT) {
         ~~~~~~~^~~~~~~~~~~~
rect.cpp:173:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(lastup < evs.size() && evs[lastup].x == c && evs[lastup].type == ERASE) {
         ~~~~~~~^~~~~~~~~~~~
rect.cpp:179:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(lastup < evs.size()) {
        ~~~~~~~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:205:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < rez.size()) {
        ~~^~~~~~~~~~~~
rect.cpp:206:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < rez.size() && rez[i].l1 == rez[j].l1 && rez[i].l2 == rez[j].l2 && rez[i].c + (j - i) == rez[j].c)
         ~~^~~~~~~~~~~~
rect.cpp:190:6: warning: variable 'N' set but not used [-Wunused-but-set-variable]
  int N, M;
      ^

• 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