oj.uz

Submission #157580

# Submission time Handle Problem Language Result Execution time Memory
157580 2019-10-12T13:34:51 Z faremy Pairs (IOI07_pairs) C++14
100 / 100
 2520 ms 311864 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 760 KB Output is correct
2 Correct 17 ms 764 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 760 KB Output is correct
2 Correct 23 ms 732 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 760 KB Output is correct
2 Correct 24 ms 760 KB Output is correct
3 Correct 23 ms 892 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10804 KB Output is correct
2 Correct 74 ms 10716 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10728 KB Output is correct
2 Correct 75 ms 10712 KB Output is correct
3 Correct 82 ms 10844 KB Output is correct
4 Correct 80 ms 10712 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10684 KB Output is correct
2 Correct 92 ms 10804 KB Output is correct
3 Correct 86 ms 10712 KB Output is correct
4 Correct 83 ms 10716 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4600 KB Output is correct
2 Correct 45 ms 5752 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 21316 KB Output is correct
2 Correct 505 ms 80100 KB Output is correct
3 Correct 921 ms 139172 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 94480 KB Output is correct
2 Correct 2303 ms 286892 KB Output is correct
3 Correct 2520 ms 309440 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1685 ms 208116 KB Output is correct
2 Correct 2472 ms 309200 KB Output is correct
3 Correct 2453 ms 311864 KB Output is correct