Submission #157580

#	Time	Username	Problem	Language	Result	Execution time	Memory
157580		faremy	Pairs (IOI07_pairs)	C++14	100 / 100	2520 ms	311864 KiB

pairs

#include <iostream>
#include <algorithm>
#include <vector>


struct Event
{
	Event(int p, int t, int l, int r, int s) : pos(p), type(t), left(l), right(r), squ(s) {}
	int pos, type, left, right, squ;

	bool operator <(const Event &other) const
	{
		if (pos != other.pos)
			return (pos < other.pos);
		return (type < other.type);
	}
};

const int MAXN = 1e5;
const int TSIZE = 5e5;

//Subtask 1
int animals[MAXN];

//Subtask 2
int tree[TSIZE];
std::vector<Event> squares;
long long first[MAXN], count[MAXN];

//Subtask 3
std::vector<Event> decomp[76];
long long cnt[MAXN];


void oned(int toys, int maxDist)
{
	for (int iToy = 0; iToy < toys; iToy++)
		std::cin >> animals[iToy];
	std::sort(animals, animals + toys);

	long long ans = 0, last = 0;
	for (long long iToy = 0; iToy < toys; iToy++)
	{
		while (animals[iToy] - animals[last] > maxDist)
			last++;
		ans += iToy - last;
	}

	std::cout << ans << '\n';
}

void add(int u)
{
	while (u < TSIZE)
	{
		tree[u]++;
		u += u & (-u);
	}
}

int sum(int u)
{
	int r = 0;
	while (u > 0)
	{
		r += tree[u];
		u -= u & (-u);
	}

	return r;
}	

void countinsqr()
{
	std::fill_n(tree, TSIZE, 0);
	std::sort(squares.begin(), squares.end());

	for (Event &ev : squares)
	{
		if (ev.type == -1)
			first[ev.squ] = sum(ev.right) - sum(ev.left);
		else if (ev.type == 1)
			count[ev.squ] = sum(ev.right) - sum(ev.left) - first[ev.squ];
		else
			add(ev.left);
	}
}

void twod(int toys, int maxDist)
{
	for (int iToy = 0; iToy < toys; iToy++)
	{
		int a, b;
		std::cin >> a >> b;
		int x = b - a, y = b + a;

		squares.emplace_back(x - maxDist, -1, y, y + 2 * maxDist + 1, iToy);
		squares.emplace_back(x + maxDist, 1, y, y + 2 * maxDist + 1, iToy);
		squares.emplace_back(x, 0, y + maxDist + 1, -1, -1);
	}

	countinsqr();
	long long ans = 0;

	for (int iToy = 0; iToy < toys; iToy++)
		ans += count[iToy] - 1LL;
	std::cout << ans / 2LL << '\n';
}

void threed(int toys, int maxDist)
{
	for (int iToy = 0; iToy < toys; iToy++)
	{
		int a, b, c;
		std::cin >> a >> b >> c;
		int x = b - a, y = b + a;

		decomp[c].emplace_back(x, 0, y + maxDist + 1, -1, -1);
		for (int iDelt = 0; iDelt <= maxDist && c > iDelt; iDelt++)
		{
			int d = maxDist - iDelt;
			decomp[c - iDelt].emplace_back(x - d, -1, y + iDelt, y + maxDist + d + 1, iToy);
			decomp[c - iDelt].emplace_back(x + d, 1, y + iDelt, y + maxDist + d + 1, iToy);
		}
		for (int iDelt = 1; iDelt <= maxDist && c + iDelt < 76; iDelt++)
		{
			int d = maxDist - iDelt;
			decomp[c + iDelt].emplace_back(x - d, -1, y + iDelt, y + maxDist + d + 1, iToy);
			decomp[c + iDelt].emplace_back(x + d, 1, y + iDelt, y + maxDist + d + 1, iToy);
		}
	}

	for (int iDepth = 1; iDepth < 76; iDepth++)
	{
		std::fill_n(count, toys, 0);
		squares = decomp[iDepth];

		countinsqr();
		for (int iToy = 0; iToy < toys; iToy++)
			cnt[iToy] += count[iToy];
	}

	long long ans = 0;
	for (int iToy = 0; iToy < toys; iToy++)
		ans += cnt[iToy] - 1LL;
	std::cout << ans / 2LL << '\n';
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int boardType, toys, maxDist, boardSize;
	std::cin >> boardType >> toys >> maxDist >> boardSize;

	if (boardType == 1)
		oned(toys, std::min(maxDist, boardSize - 1));
	else if (boardType == 2)
		twod(toys, std::min(maxDist, (boardSize - 1) * 2));
	else
		threed(toys, std::min(maxDist, (boardSize - 1) * 3));

	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10