Submission #285232

#	Time	Username	Problem	Language	Result	Execution time	Memory
285232		cookiedoth	Rectangles (IOI19_rect)	C++14	100 / 100	3939 ms	527648 KiB

rect

/*

Code for problem C by cookiedoth
Generated 28 Aug 2020 at 01.11 PM


СТРОИМ КОММУНИЗМ РАБОТЯГИ!
 
                                    ╦═╩═╦═╩═█
                          ████▄▄▄═╦═╩═╦═╩═╦═█
                  ████████████████▄▄╦═╩═╦═╩═█
█═╦═╩═╦▄████████████████▀▀▀▀█████████▄╦═╩═╦═█
█═╩═╦═████████████████████▄═╦▀█████████═╦═╩═█
█═╦═▄██████████▀╩═╦═╩▄██████▄═╦▀████████▄═╦═█
█═╩═█████████▀╩═╦═╩═█████████▄╩═╦████████═╩═█
█═╦█████████▄═╦═╩═╦═▀█████████╦═╩═████████╦═█
█═╩███████████▄▄██▄═╦═▀████████═╦═████████╩═█
█═██████████████████▄═╦═▀█████▀═╩═█████████═█
█═████████████████████▄═╦═▀███╩═╦═█████████═█
█═╦████████████▀╩▀██████▄═╦═▀═╦═╩█████████╦═█
█═╩█████████▀═╩═╦═╩▀▀███▀▀╩═╦═╩═██████████╩═█
█═╦═██████▀═╦═▄▄█▄▄═╩═╦═╩═╦═╩═╦═╩▀███████═╦═█
█═╩═▀████═╩═▄█████████▄▄▄▄████▄═╦═╩█████▀═╩═█
█═╦═╩═██████████████████████████▄═▄████═╩═╦═█
█═╩═╦═╩▀█████████████████████████████▀╩═╦═╩═█
█═╦═╩═╦═╩▀▀███████████████████████▀▀╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═▀▀▀███████████████▀▀▀═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═▀▀▀▀▀▀▀▀▀═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█

o_O
^_^
~_^

*/

#include "rect.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

struct segment {
	int l, r, type, dp;
	segment(int _l, int _r): l(_l), r(_r), dp(0), type(0) {}
};

ostream& operator << (ostream &os, const segment &s) {
	os << s.l << ' ' << s.r << ' ' << s.type << ' ' << s.dp << '\n';
	return os;
}

bool operator < (const segment &a, const segment &b) {
	return make_pair(a.l, make_pair(a.r, a.type)) < make_pair(b.l, make_pair(b.r, b.type));
}

void find_segments(const vector<int> &arr, vector<segment> &vs) {
	// cerr << "find_segments" << endl;
	// output(all(arr));
	vector<int> rb;
	int len = arr.size();
	vector<int> st;
	for (int i = len - 1; i >= 0; --i) {
		rb.clear();
		int eq = 0;
		while (!st.empty() && arr[i] >= arr[st.back()]) {
			if (arr[i] == arr[st.back()]) {
				eq = 1;
			}
			rb.push_back(st.back());
			st.pop_back();
		}
		if (!st.empty() && !eq) {
			rb.push_back(st.back());
		}
		st.push_back(i);
		reverse(all(rb));
		for (auto r : rb) {
			if (r - 1 >= i + 1) {
				vs.emplace_back(i + 1, r - 1);
			}
		}
	}
	reverse(all(vs));
}

void calc_dp(vector<vector<segment> > &vvs) {
	for (int i = (int)vvs.size() - 2; i >= 1; --i) {
		for (auto &seg : vvs[i]) {
			auto it = lower_bound(all(vvs[i + 1]), seg);
			if (it != vvs[i + 1].end() && seg.l == it->l && seg.r == it->r) {
				seg.dp = it->dp + 1;
			} else {
				seg.dp = 1;
			}
		}
	}
}

int n, m;
vector<vector<int> > a, _a;
vector<vector<segment> > row_s, col_s;
ll ans;

void transpose_a() {
	_a.resize(m, vector<int> (n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			_a[j][i] = a[i][j];
		}
	}
}

void find_segments() {
	row_s.resize(n);
	for (int i = 1; i < n - 1; ++i) {
		find_segments(a[i], row_s[i]);
	}
	transpose_a();
	col_s.resize(m);
	for (int i = 1; i < m - 1; ++i) {
		find_segments(_a[i], col_s[i]);
	}
}

void calc_dp() {
	calc_dp(row_s);
	calc_dp(col_s);
}

void add_fake_segments() {
	for (int i = 1; i <= n - 2; ++i) {
		for (auto seg : row_s[i]) {
			segment cur(i, i + seg.dp - 1);
			cur.type = 1;
			cur.dp = -(seg.r - seg.l + 1);
			col_s[seg.l].push_back(cur);
		}
	}
	for (int i = 1; i <= m - 2; ++i) {
		sort(all(col_s[i]));
	}
}

struct fenwick {
	vector<int> t, used;
	int n, used_clr;

	void refresh(int pos) {
		if (used[pos] != used_clr) {
			used[pos] = used_clr;
			t[pos] = 0;
		}
	}

	void clear() {
		used_clr++;
	}
	
	void init(int _n) {
		n = _n;
		t.resize(n);
		used.resize(n);
	}

	void add(int pos, int val) {
		while (pos < n) {
			refresh(pos);
			t[pos] += val;
			pos = (pos | (pos + 1));
		}
	}

	int get(int r) {
		int res = 0;
		while (r >= 0) {
			refresh(r);
			res += t[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}

	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

void scanline() {
	fenwick f;
	f.init(m + 1);
	for (int i = 1; i <= m - 2; ++i) {
		f.clear();
		for (int j = 0; j < (int)col_s[i].size(); ++j) {
			if (col_s[i][j].type == 1) {
				ans += f.get(-col_s[i][j].dp, m);
			} else {
				f.add(col_s[i][j].dp, 1);
			}
			if (j < (int)col_s[i].size() - 1 && col_s[i][j].l != col_s[i][j + 1].l) {
				f.clear();
			}
		}
	}
}

ll count_rectangles(vector<vector<int> > _a0) {
	a = _a0;
	n = a.size();
	m = a[0].size();
	find_segments();
	calc_dp();
	add_fake_segments();
	scanline();
	return ans;
}

Compilation message (stderr)

rect.cpp: In constructor 'segment::segment(int, int)':
rect.cpp:108:18: warning: 'segment::dp' will be initialized after [-Wreorder]
  108 |  int l, r, type, dp;
      |                  ^~
rect.cpp:108:12: warning:   'int segment::type' [-Wreorder]
  108 |  int l, r, type, dp;
      |            ^~~~
rect.cpp:109:2: warning:   when initialized here [-Wreorder]
  109 |  segment(int _l, int _r): l(_l), r(_r), dp(0), type(0) {}
      |  ^~~~~~~

• 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