Submission #1017521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017521		BestCrazyNoob	Rectangles (IOI19_rect)	C++17	100 / 100	3444 ms	419044 KiB

rect

#include "rect.h"
#include <utility>
#include <tuple>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
constexpr int MAXN = 2'500;

int N, M;

struct SegTreeMax {
	int sz;
	vector<pii> tree; // min, index (min(a, b) works)
	int ql, qr;
	void merge(int i) {
		tree[i] = max(tree[2*i], tree[2*i+1]);
	}
	SegTreeMax(vector<int> V) {
		sz = 1;
		while (sz < V.size()) sz *= 2;
		tree.resize(2*sz);
		for (int i = 0; i < V.size(); i++) tree[sz+i] = {V[i], i};
		for (int i = V.size(); i < sz; i++) tree[sz+i] = {-1, -1};
		for (int i = sz-1; i >= 1; i--) merge(i);
	}
	pii __query(int ni, int nl, int nr) {
		if (qr <= nl || nr <= ql) return {-1, -1};
		if (ql <= nl && nr <= qr) return tree[ni];
		int nm = (nl+nr)/2;
		return max(__query(2*ni, nl, nm), __query(2*ni+1, nm, nr));
	}
	pii query(int l, int r) {
		ql = l;
		qr = r;
		return __query(1, 0, sz);
	}
};

struct treap {
    treap *L, *R;
    int key, pri;
    int sz;
	treap() {}
    treap(int x): L(nullptr), R(nullptr), key(x), pri(rand()), sz(1) {}
    treap *join(treap *L, treap *R) {
        this->L = L;
        this->R = R;
        sz = 1+ (L ? L->sz : 0) + (R ? R->sz : 0);
        return this;
    }
};

treap* merge(treap *L, treap *R) {
    if (!L) return R;
    if (!R) return L;
    if (L->pri > R->pri) {
        return L->join(L->L, merge(L->R, R));
    } else {
        return R->join(merge(L, R->L), R->R);
    }
}

pair<treap*, treap*> split(treap *T, int x) {
    if (!T) return {nullptr, nullptr};
    if (x <= T->key) {
        auto [LL, LR] = split(T->L, x);
        return {LL, T->join(LR, T->R)};
    } else {
        auto [RL, RR] = split(T->R, x);
        return {T->join(T->L, RL), RR};
    }
}

treap prealloc[10'000];
int nxtPrealloc;

treap* insert(treap *T, int x) {
    auto [L, R] = split(T, x);
	prealloc[nxtPrealloc++] = treap(x);
    return merge(L, merge(prealloc + nxtPrealloc - 1, R));
}

// 0 - excl
ll query(treap *T, int r) {
    auto [L, R] = split(T, r);
    ll res = L ? L->sz : 0;
    T = merge(L, R);
    return res;
}


// excluded - excluded, because the last element on both sides is the border
vector<pii> splits(vector<int> V) {
	// TODO: pay attention to equal elements. If there are multiples, return the rightmost.
	SegTreeMax seg(V);
	vector<pii> res;
	function<void(int, int, bool, bool)> rec = [&](int l, int r, bool lGood, bool rGood) {
		// Exit condition
		if (l == r) return;
		// Check that the extremes are actual elements
		if (l != 0 && r != V.size()) res.push_back({l-1, r});
		if (l+1 == r) return;
		auto [mx, mxi] = seg.query(l, r); // rightmost max
		rec(mxi+1, r, true, rGood);
		int lastMxi = mxi;
		// iterate from right to left
		while (true) {
			auto [nxtMx, nxtMxi] = seg.query(l, lastMxi);
			if (nxtMx != mx) break;
			rec(nxtMxi+1, lastMxi, true, true);
			lastMxi = nxtMxi;
		}
		rec(l, lastMxi, lGood, true);
	};
	rec(0, V.size(), false, false);
	return res;
}

long long count_rectangles(vector<vector<int>> a) {
	N = a.size();
	M = a[0].size();
	vector<vector<int>> a2(M, vector<int>(N));
	vector<vector<vector<int>>> grid(N, vector<vector<int>>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			a2[j][i] = a[i][j];
		}
	}
	for (int j = 0; j < M; j++) {
		for (auto [s, e]: splits(a2[j])) {
			grid[e][j].push_back(s);
		}
	}
	vector<vector<pii>> active(M, vector<pii>(M, {-2, -2})); // (incl, incl)
	long long ans = 0;
	for (int i = 1; i < N-1; i++) {
		vector<pii> x = splits(a[i]);
		vector<vector<int>> byEnd(M);
		vector<pii> cleanup;
		vector<pii> active2(N, {-2, -2});
		for (auto[s, e]: x) {
			if (active[s][e].second == i-1) {
				// extend
				active[s][e].second = i;
			} else {
				// start again
				active[s][e] = {i, i};
			}
			byEnd[e].push_back(s);
		}
		for (int j = 1; j < M; j++) {
			sort(grid[i+1][j-1].rbegin(), grid[i+1][j-1].rend());
			sort(byEnd[j].begin(), byEnd[j].end(), [&](int a, int b) {return active[a][j].first > active[b][j].first;});
			for (auto e: grid[i+1][j-1]) {
				// same idea as above
				if (active2[e].second == j-2) active2[e].second = j-1;
				else active2[e] = {j-1, j-1};
			}
			nxtPrealloc = 0; // Treap prealloc
			treap* T = nullptr;
			for (int a = 0, b = 0; b < byEnd[j].size(); b++) {
				// TODO: might have to use a treap / sparse tree
				while (a < grid[i+1][j-1].size() && grid[i+1][j-1][a] >= active[byEnd[j][b]][j].first - 1) {
					T = insert(T, active2[grid[i+1][j-1][a]].first);
					a++;
				}
				for (int idx = 0; idx < a; idx++) {
					/* if (active2[grid[i+1][j-1][idx]].first <= byEnd[j][b]+1) {
						ans++;
					} */
				}
				ans += query(T, byEnd[j][b]+2); // excluded
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In constructor 'SegTreeMax::SegTreeMax(std::vector<int>)':
rect.cpp:24:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   while (sz < V.size()) sz *= 2;
      |          ~~~^~~~~~~~~~
rect.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int i = 0; i < V.size(); i++) tree[sz+i] = {V[i], i};
      |                   ~~^~~~~~~~~~
rect.cpp: In lambda function:
rect.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   if (l != 0 && r != V.size()) res.push_back({l-1, r});
      |                 ~~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:165:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |    for (int a = 0, b = 0; b < byEnd[j].size(); b++) {
      |                           ~~^~~~~~~~~~~~~~~~~
rect.cpp:167:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     while (a < grid[i+1][j-1].size() && grid[i+1][j-1][a] >= active[byEnd[j][b]][j].first - 1) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~

• 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