oj.uz

Submission #157576

# Submission time Handle Problem Language Result Execution time Memory
157576 2019-10-12T13:22:06 Z faremy Pairs (IOI07_pairs) C++14
60 / 100
 92 ms 14300 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[MAXN];
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)
{

}

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 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3636 KB Output is correct
2 Correct 19 ms 3556 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3964 KB Output is correct
2 Correct 29 ms 3920 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3960 KB Output is correct
2 Correct 27 ms 4048 KB Output is correct
3 Correct 25 ms 3960 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 7 ms 4856 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 13656 KB Output is correct
2 Correct 77 ms 13744 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 13916 KB Output is correct
2 Correct 78 ms 13916 KB Output is correct
3 Correct 78 ms 13916 KB Output is correct
4 Correct 78 ms 13916 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 14256 KB Output is correct
2 Correct 89 ms 14192 KB Output is correct
3 Correct 84 ms 14300 KB Output is correct
4 Correct 85 ms 14300 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -