oj.uz

Submission #377265

# Submission time Handle Problem Language Result Execution time Memory
377265 2021-03-13T15:20:41 Z Berted Pairs (IOI07_pairs) C++14
100 / 100
 370 ms 9836 KB 
#include <iostream>
#include <algorithm>
#include <queue>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;

int B, N, D, M;

namespace solve1D // O(N log N)
{
	int A[100001];
	inline ll solve()
	{
		ll ret = 0;
		for (int i = 0; i < N; i++) cin >> A[i];
		sort(A, A + N);
		int j = 0;
		for (int i = 1; i < N; i++)
		{
			while (j < i && A[j] + D < A[i]) {j++;}
			ret += i - j;
		}
		return ret;
	}
}

namespace solve2D // O(N log M)
{
	pii A[100001]; int BIT[150001];

	inline void upd(int x, int v)
	{
		for (; x <= 2 * M; x += x & (-x)) {BIT[x] += v;}
	}

	inline int qry(int x)
	{
		int ret = 0;
		x = min(x, 2 * M); x = max(x, 0);
		for (; x; x -= x & (-x)) {ret += BIT[x];}
		return ret;
	}

	inline ll solve()
	{
		ll ret = 0;

		for (int i = 0; i < N; i++)
		{
			int x, y; cin >> x >> y;
			A[i] = {x - y, x + y};
		}
		sort(A, A + N);

		int j = 0;
		for (int i = 0; i < N; i++)
		{
			while (j < i && A[j].fst + D < A[i].fst) 
				upd(A[j++].snd, -1);
			ret += qry(A[i].snd + D) - qry(A[i].snd - D - 1);
			upd(A[i].snd, 1);
		}

		return ret;
	}
}

namespace solve3D // O(M^3 + NM)
{
	int A[100001][3], pref[80][160][160];

	inline void process(int l)
	{
		for (int i = 0; i <= 2 * M; i++)
		{
			for (int j = 0; j <= 2 * M; j++)
			{
				if (i) pref[l][i][j] += pref[l][i - 1][j];
				if (j) pref[l][i][j] += pref[l][i][j - 1];
				if (i && j) pref[l][i][j] -= pref[l][i - 1][j - 1];
			}
		}
	}

	inline int qry(int l, int x1, int y1, int x2, int y2)
	{
		x1 = max(x1 - 1, 0); y1 = max(y1 - 1, 0);
		x2 = min(x2, 2 * M); y2 = min(y2, 2 * M);
		return pref[l][x2][y2] - pref[l][x1][y2] - pref[l][x2][y1] + pref[l][x1][y1];
	}

	inline ll solve()
	{
		ll ret = 0;
		for (int i = 0; i < N; i++)
		{
			int x, y; cin >> A[i][0] >> x >> y;
			A[i][1] = x - y + M; A[i][2] = x + y; 
			pref[A[i][0]][A[i][1]][A[i][2]]++;
		}
		for (int i = 1; i <= M; i++) process(i);
		for (int i = 0; i < N; i++)
			for (int j = 1; j <= M; j++)
			{
				int d = D - abs(j - A[i][0]);
				if (d >= 0) ret += qry(j, A[i][1] - d, A[i][2] - d, A[i][1] + d, A[i][2] + d);
			}
		
		return (ret - N) / 2; 
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> B >> N >> D >> M;
	if (B == 1) cout << solve1D :: solve() << "\n";
	else if (B == 2) cout << solve2D :: solve() << "\n";
	else cout << solve3D :: solve() << "\n";
	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1608 KB Output is correct
2 Correct 20 ms 1644 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1772 KB Output is correct
2 Correct 22 ms 1772 KB Output is correct
3 Correct 19 ms 1644 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1772 KB Output is correct
2 Correct 26 ms 1772 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1900 KB Output is correct
2 Correct 31 ms 1900 KB Output is correct
3 Correct 32 ms 1900 KB Output is correct
4 Correct 31 ms 1900 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2796 KB Output is correct
2 Correct 36 ms 2796 KB Output is correct
3 Correct 38 ms 2796 KB Output is correct
4 Correct 37 ms 3052 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7532 KB Output is correct
2 Correct 12 ms 7532 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2284 KB Output is correct
2 Correct 28 ms 2284 KB Output is correct
3 Correct 27 ms 2412 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7148 KB Output is correct
2 Correct 175 ms 7276 KB Output is correct
3 Correct 91 ms 7148 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 9660 KB Output is correct
2 Correct 370 ms 9836 KB Output is correct
3 Correct 119 ms 9580 KB Output is correct