제출 #817347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817347		prvocislo	Rectangles (IOI19_rect)	C++17	72 / 100	5100 ms	887052 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll ans = 0;
struct obdl
{
	int x1, y1, x2, y2, t;
};
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];
void upd(int i, int x)
{
	for (; i < maxn; i = (i | (i + 1))) st[i] += x;
}
int query(int r)
{
	int ans = 0;
	for (; r >= 0; r = (r & (r + 1)) - 1) ans += st[r];
	return ans;
}
struct udaj { int x, y, 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<vector<vector<obdl> > > o(n, vector<vector<obdl> >(m));
	vector<obdl> o1 = make(a);
	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) i.t = 2, swap(i.x1, i.y1), swap(i.x2, i.y2), o[i.x2][i.y2].push_back(i);
	for (obdl i : o1) i.t = 1, o[i.x2][i.y2].push_back(i);
	for (int x = 0; x < n; x++) for (int y = m - 1; y >= 0; y--) for (obdl i : o[x][y])
	{
		if (i.t == 1) for (int x1 = i.x1; x1 <= i.x2; x1++) v[x1][i.y1].push_back({ x, y, 1 });
		if (i.t == 2) for (int y1 = i.y1; y1 <= i.y2; y1++) v[i.x1][y1].push_back({ x, y, 2 });
	}
	ll ans = 0;
	for (int x = 1; x + 1 < n; x++) for (int y = 1; y + 1 < m; y++)
	{
		ll sum = 0, all = 0;
		for (udaj u : v[x][y])
		{
			if (u.t == 2) upd(u.y, 1), all++;
			else sum += all - query(u.y - 1);
		}
		for (udaj u : v[x][y]) if (u.t == 2) upd(u.y, -1);
		ans += sum;
		//cout << sum << " \n"[y == m - 2];
	}
	return ans;
}

• 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: 0 / 28