Submission #146023

#	Time	Username	Problem	Language	Result	Execution time	Memory
146023		jwvg0425	Rectangles (IOI19_rect)	C++17	100 / 100	4652 ms	784632 KiB

rect

#include "rect.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <stack>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MAXL 2505

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

class FenwickTree
{
public:
	FenwickTree(int k)
	{
		data.resize(k);
	}

	i64 sum(int n)
	{
		i64 ans = 0;

		while (n > 0)
		{
			ans += data[n];
			n -= (n & -n);
		}

		return ans;
	}

	void add(int n, i64 num)
	{
		while (n < data.size())
		{
			data[n] += num;
			n += (n & -n);
		}
	}

private:
	vector<i64> data;
};

// (구간 길이, 반대편 확장 가능 길이)
vector<ii> rseg[MAXL][MAXL];
vector<ii> dseg[MAXL][MAXL];

long long count_rectangles(vector<vector<int>> a) 
{
	i64 ans = 0;
	int n = a.size();
	int m = a[0].size();

	for (int x = 0; x < n; x++)
	{
		stack<int> s;

		for (int y = 0; y < m; y++)
		{
			while (!s.empty() && a[x][s.top()] <= a[x][y])
			{
				int l = y - s.top() - 1;
				if (l > 0)
					rseg[x][s.top()].emplace_back(l, 1);

				s.pop();
			}

			s.push(y);
		}

		stack<int> s2;

		for (int y = m - 1; y >= 0; y--)
		{
			while (!s2.empty() && a[x][s2.top()] <= a[x][y])
			{
				int l = s2.top() - y - 1;
				if (a[x][s2.top()] != a[x][y] && l > 0)
					rseg[x][y].emplace_back(l, 1);

				s2.pop();
			}
			s2.push(y);
		}
	}

	for (int y = 0; y < m; y++)
	{
		stack<int> s;
		for (int x = 0; x < n; x++)
		{
			while (!s.empty() && a[s.top()][y] <= a[x][y])
			{
				int l = x - s.top() - 1;
				if (l > 0)
					dseg[s.top()][y].emplace_back(l, 1);

				s.pop();
			}

			s.push(x);
		}

		stack<int> s2;

		for (int x = n - 1; x >= 0; x--)
		{
			while (!s2.empty() && a[s2.top()][y] <= a[x][y])
			{
				int l = s2.top() - x - 1;
				if (a[s2.top()][y] != a[x][y] && l > 0)
					dseg[x][y].emplace_back(l, 1);

				s2.pop();
			}
			s2.push(x);
		}
	}

	for (int x = 0; x < n; x++)
	{
		for (int y = 0; y < m; y++)
		{
			sort(all(rseg[x][y]));
			sort(all(dseg[x][y]));
		}
	}

	for (int y = 0; y < m; y++)
	{
		for (int x = n - 2; x >= 0; x--)
		{
			for (auto& rv : rseg[x][y])
			{
				auto iter = lower_bound(all(rseg[x + 1][y]), rv);

				if (iter != rseg[x + 1][y].end() && iter->xx == rv.xx)
					rv.yy = iter->yy + 1;
			}
		}
	}

	for (int x = 0; x < n; x++)
	{
		for (int y = m - 2; y >= 0; y--)
		{
			for (auto& dv : dseg[x][y])
			{
				auto iter = lower_bound(all(dseg[x][y + 1]), dv);

				if (iter != dseg[x][y + 1].end() && iter->xx == dv.xx)
					dv.yy = iter->yy + 1;
			}
		}
	}

	for (int x = 0; x < n; x++)
	{
		for (int y = 0; y < m; y++)
		{
			sort(all(rseg[x][y]), [](const ii& l, const ii& r) { return l.yy < r.yy; });
			sort(all(dseg[x][y]));
		}
	}

	FenwickTree tree(2505);

	for (int x = 1; x < n - 1; x++)
	{
		for (int y = 1; y < m - 1; y++)
		{
			int didx = 0;

			for (auto& ri : rseg[x][y - 1])
			{
				while (didx < dseg[x - 1][y].size() && dseg[x - 1][y][didx].xx <= ri.yy)
				{
					tree.add(dseg[x - 1][y][didx].yy, 1);
					didx++;
				}

				ans += tree.sum(2503) - tree.sum(ri.xx - 1);
			}

			for (int dx = 0; dx < didx; dx++)
				tree.add(dseg[x - 1][y][dx].yy, -1);
		}
	}

	return ans;
}

Compilation message (stderr)

rect.cpp: In member function 'void FenwickTree::add(int, i64)':
rect.cpp:53:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (n < data.size())
          ~~^~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:197:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (didx < dseg[x - 1][y].size() && dseg[x - 1][y][didx].xx <= ri.yy)
            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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