Submission #377265

#	Time	Username	Problem	Language	Result	Execution time	Memory
377265		Berted	Pairs (IOI07_pairs)	C++14	100 / 100	370 ms	9836 KiB

pairs

#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 / 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