Submission #817102

#	Time	Username	Problem	Language	Result	Execution time	Memory
817102		prvocislo	Rectangles (IOI19_rect)	C++17	Compilation error	0 ms	0 KiB

rect

#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

ll ans = 0;
struct obdl
{
	int x1, y1, x2, y2;
};
vector<obdl> make(vector<vector<int> > a)
{
	int n = a.size(), m = a[0].size();
	vector<set<pair<int, int> > > end(n);
	for (int i = 0; i < n; i++)
	{ 
		vector<int> ri(m, m), li(m, -1);
		vector<int> st;
		for (int j = 0; j < m; j++) // najdeme najblizsi vacsi
		{
			while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
			if (!st.empty() && st.back() + 1 < j) li[j] = st.back();
			st.push_back(j);
		}
		st.clear();
		for (int j = m - 1; j >= 0; j--) // najdeme najblizsi vacsi
		{
			while (!st.empty() && a[i][j] > a[i][st.back()]) st.pop_back();
			if (!st.empty() && st.back() - 1 > j) ri[j] = st.back();
			st.push_back(j);
		}
		for (int j = 0; j < m; j++)
		{
			if (ri[j] != m && li[ri[j]] <= j) end[i].insert({ j + 1, ri[j] - 1 });
			if (li[j] != -1 && ri[li[j]] >= j) end[i].insert({ li[j] + 1, j - 1 });
		}
	}
	vector<obdl>o;
	for (int i = 0; i < n; i++) for (pair<int, int> p : end[i])
	{
		int j = i + 1;
		while (j < n && end[j].count(p)) end[j++].erase(p);
		o.push_back({ i, p.first, j - 1, p.second });
	}
	return o;
}
const int maxn = 2505;
int st[maxn * 2];
void upd(int i, int x)
{
	for (i += maxn; i > 0; i >>= 1) st[i] += x;
}
int query(int l, int r)
{
	int ans = 0;
	for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1) ans += st[l++];
		if (r & 1) ans += st[--r];
	}
	return ans;
}
struct udaj { int x, y, t; };
bool cmp(udaj a, udaj b)
{
	if (a.x != b.x) return a.x < b.x;
	return a.t > b.t;
}
ll count_rectangles(vector<vector<int> > a)
{
	int n = a.size(), m = a[0].size();
	vector<vector<vector<udaj> > > v(n, vector<vector<udaj> >(m));
	vector<obdl> o1 = make(a);
	for (obdl o : o1) for (int x = o.x1; x <= o.x2; x++) v[x][o.y1].push_back({ o.x2, o.y2, 1 });
	vector<vector<int> > b(m, vector<int>(n));
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[j][i] = a[i][j];
	vector<obdl> o2 = make(b);
	for (obdl& i : o2) swap(i.x1, i.y1), swap(i.x2, i.y2);
	for (obdl o : o2) for (int y = o.y1; y <= o.y2; y++) v[o.x1][y].push_back({ o.x2, o.y2, 2 });
	ll ans = 0;
	for (int x = 0; x < n; x++) for (int y = 0; y < m; y++)
	{
		sort(v[x][y].begin(), v[x][y].end(), cmp);
		ll sum = 0;
		for (udaj u : v[x][y])
		{
			if (u.t == 2) upd(u.y, 1);
			else sum += query(u.y, maxn - 1);
		}
		for (udaj u : v[x][y]) if (u.t == 2) upd(u.y, -1);
		ans += sum;
		cout << sum << " \n"[y == m - 1];
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:90:3: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   90 |   sort(v[x][y].begin(), v[x][y].end(), cmp);
      |   ^~~~
      |   qsort