Submission #152961

#	Time	Username	Problem	Language	Result	Execution time	Memory
152961		luciocf	Pairs (IOI07_pairs)	C++14	60 / 100	292 ms	4288 KiB

pairs

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
const int maxn = 4e5+10;
const int add1 = 2e5+10;

const int maxn2 = 455;
const int add2 = 230;

struct Pt
{
	int x, y, z;
} p[maxn];

bool comp(Pt a, Pt b)
{
	return a.x < b.x;
}
 
pii a[maxn];
 
int bit_1d[2][maxn];
int bit_2d[3][455][455];
 
void upd_1d(int x, int v, int q)
{
	if (!x) return;
 
	for (; x < maxn; x += (x&-x))
		bit_1d[q][x] += v;
}
 
int soma_1d(int x, int q)
{
	int ans = 0;
	for (; x > 0; x -= (x&-x))
		ans += bit_1d[q][x];
	return ans;
}

void upd_2d(int x, int y, int v, int q)
{
	for (int i = x; i < maxn2; i += (i&-i))
		for (int j = y; j < maxn2; j += (j&-j))
			bit_2d[q][i][j] += v;
}

int soma_2d(int x, int y, int q)
{
	int ans = 0;
	for (int i = x; i > 0; i -= (i&-i))
		for (int j = y; j > 0; j -= (j&-j))
			ans += bit_2d[q][i][j];
	return ans;
}
 
long long solve_1(void)
{
	int n, d, m;
	scanf("%d %d %d", &n, &d, &m);
 
	int x[n+1];
 
	for (int i = 1; i <= n; i++)
		scanf("%d", &x[i]);
 
	sort(x+1, x+n+1);
 
	long long ans = 0;
 
	int l = 1, r = 2;
	while (l <= n && r <= n)
	{
		if (l != r && x[r]-x[l] <= d)
			ans += 1ll*(r-l);
 
		if (x[r]-x[l] <= d) r++;
		else l++;
	}
 
	return ans;
}
 
long long solve_2(void)
{
	int n, D, m;
	scanf("%d %d %d", &n, &D, &m);
 
	for (int i = 1; i <= n; i++)
		scanf("%d %d", &a[i].first, &a[i].second);
 
	sort(a+1, a+n+1);
 
	long long ans = 0;
	int ptr = 1;
 
	upd_1d(a[1].first+a[1].second+add1, 1, 0);
	upd_1d(a[1].second+add1, 1, 1);
 
	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && a[i].first-a[ptr].first > D)
		{
			upd_1d(a[ptr].first+a[ptr].second+add1, -1, 0);
			upd_1d(a[ptr].second+add1, -1, 1);
 
			ptr++;
		}
 
		if (i != ptr)
		{
			ans += 1ll*(soma_1d(maxn-1, 0)-soma_1d(a[i].first+a[i].second-D-1+add1, 0));
			ans -= 1ll*(soma_1d(maxn-1, 1)-soma_1d(a[i].second+add1, 1));
		}
 
		upd_1d(a[i].first+a[i].second+add1, 1, 0);
		upd_1d(a[i].second+add1, 1, 1);
	}
 
	memset(bit_1d, 0, sizeof bit_1d);
 
	ptr = 1;
 
	upd_1d(a[1].first-a[1].second+add1, 1, 0);
	upd_1d(a[1].second+add1, 1, 1);
 
	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && a[i].first-a[ptr].first > D)
		{
			upd_1d(a[ptr].first-a[ptr].second+add1, -1, 0);
			upd_1d(a[ptr].second+add1, -1, 1);
 
			ptr++;
		}
 
		if (i != ptr)
		{
			ans += 1ll*(soma_1d(maxn-1, 0)-soma_1d(a[i].first-a[i].second-D-1+add1, 0));
			ans -= 1ll*soma_1d(a[i].second+add1, 1);
		}
 
		upd_1d(a[i].first-a[i].second+add1, 1, 0);
		upd_1d(a[i].second+add1, 1, 1);
	}
 
	return ans;
}

int get_rect(int x1, int y1, int x2, int y2, int q)
{
	return (soma_2d(x2, y2, q)-soma_2d(x1-1, y2, q)-soma_2d(x2, y1-1, q)+soma_2d(x1-1, y1-1, q));
}

long long solve_3(void)
{
	int n, D, m;
	scanf("%d %d %d", &n, &D, &m);
 
	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);

	sort(p+1, p+n+1, comp);

	long long ans = 0;
	int ptr = 1;

	upd_2d(p[1].y+add2, p[1].x+p[1].y+p[1].z+add2, 1, 0);
	upd_2d(p[1].z+add2, p[1].x+p[1].y+p[1].z+add2, 1, 1);
	upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);

	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && p[i].x-p[ptr].x > D)
		{
			upd_2d(p[ptr].y+add2, p[ptr].x+p[ptr].y+p[ptr].z+add2, -1, 0);
			upd_2d(p[ptr].z+add2, p[ptr].x+p[ptr].y+p[ptr].z+add2, -1, 1);
			upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
 
			ptr++;
		}

		if (i != ptr)
		{
			ans += 1ll*get_rect(1+add2, p[i].x+p[i].y+p[i].z-D+add2, p[i].y+add2, maxn2-1, 0);
			ans -= 1ll*get_rect(p[i].z+1+add2, p[i].x+p[i].y+p[i].z-D+add2, maxn2-1, maxn2-1, 1);
			ans += 1ll*get_rect(p[i].y+1+add2, p[i].z+1+add2, maxn2-1, maxn2-1, 2);
		}

		upd_2d(p[i].y+add2, p[i].x+p[i].y+p[i].z+add2, 1, 0);
		upd_2d(p[i].z+add2, p[i].x+p[i].y+p[i].z+add2, 1, 1);
		upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
	}

	memset(bit_2d, 0, sizeof bit_2d);

	ptr = 1;

	upd_2d(p[1].y+add2, p[1].x+p[1].y-p[1].z+add2, 1, 0);
	upd_2d(p[1].z+add2, p[1].x+p[1].y-p[1].z+add2, 1, 1);
	upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);

	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && p[i].x-p[ptr].x > D)
		{
			upd_2d(p[ptr].y+add2, p[ptr].x+p[ptr].y-p[ptr].z+add2, -1, 0);
			upd_2d(p[ptr].z+add2, p[ptr].x+p[ptr].y-p[ptr].z+add2, -1, 1);
			upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
 
			ptr++;
		}

		if (i != ptr)
		{
			ans += 1ll*get_rect(1+add2, p[i].x+p[i].y-p[i].z-D+add2, p[i].y+add2, maxn2-1, 0);
			ans -= 1ll*get_rect(1+add2, p[i].x+p[i].y-p[i].z-D+add2, p[i].z+add2, maxn2-1, 1);
			ans += 1ll*get_rect(p[i].y+1+add2, 1+add2, maxn2-1, p[i].z+add2, 2);
		}

		upd_2d(p[i].y+add2, p[i].x+p[i].y-p[i].z+add2, 1, 0);
		upd_2d(p[i].z+add2, p[i].x+p[i].y-p[i].z+add2, 1, 1);
		upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
	}

	memset(bit_2d, 0, sizeof bit_2d);

	ptr = 1;

	upd_2d(p[1].y+add2, p[1].x-p[1].y+p[1].z+add2, 1, 0);
	upd_2d(p[1].z+add2, p[1].x-p[1].y+p[1].z+add2, 1, 1);
	upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);

	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && p[i].x-p[ptr].x > D)
		{
			upd_2d(p[ptr].y+add2, p[ptr].x-p[ptr].y+p[ptr].z+add2, -1, 0);
			upd_2d(p[ptr].z+add2, p[ptr].x-p[ptr].y+p[ptr].z+add2, -1, 1);
			upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
 
			ptr++;
		}

		if (i != ptr)
		{
			ans += 1ll*get_rect(p[i].y+1+add2, p[i].x-p[i].y+p[i].z-D+add2, maxn2-1, maxn2-1, 0);
			ans -= 1ll*get_rect(p[i].z+1+add2, p[i].x-p[i].y+p[i].z-D+add2, maxn2-1, maxn2-1, 1);
			ans += 1ll*get_rect(1+add2, p[i].z+1+add2, p[i].y+add2, maxn2-1, 2);
		}

		upd_2d(p[i].y+add2, p[i].x-p[i].y+p[i].z+add2, 1, 0);
		upd_2d(p[i].z+add2, p[i].x-p[i].y+p[i].z+add2, 1, 1);
		upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
	}

	memset(bit_2d, 0, sizeof bit_2d);

	ptr = 1;

	upd_2d(p[1].y+add2, p[1].x-p[1].y-p[1].z+add2, 1, 0);
	upd_2d(p[1].z+add2, p[1].x-p[1].y-p[1].z+add2, 1, 1);
	upd_2d(p[1].y+add2, p[1].z+add2, 1, 2);

	for (int i = 2; i <= n; i++)
	{
		while (ptr < i && p[i].x-p[ptr].x > D)
		{
			upd_2d(p[ptr].y+add2, p[ptr].x-p[ptr].y+p[ptr].z+add2, -1, 0);
			upd_2d(p[ptr].z+add2, p[ptr].x-p[ptr].y+p[ptr].z+add2, -1, 1);
			upd_2d(p[ptr].y+add2, p[ptr].z+add2, -1, 2);
 
			ptr++;
		}

		if (i != ptr)
		{
			ans += 1ll*get_rect(p[i].y+1+add2, p[i].x-p[i].y-p[i].z-D+add2, maxn2-1, maxn2-1, 0);
			ans -= 1ll*get_rect(1+add2, p[i].x-p[i].y-p[i].z-D+add2, p[i].z+add2, maxn2-1, 1);
			ans += 1ll*get_rect(1+add2, 1+add2, p[i].y+add2, p[i].z+add2, 2);
		}

		upd_2d(p[i].y+add2, p[i].x-p[i].y-p[i].z+add2, 1, 0);
		upd_2d(p[i].z+add2, p[i].x-p[i].y-p[i].z+add2, 1, 1);
		upd_2d(p[i].y+add2, p[i].z+add2, 1, 2);
	}

	return ans;
}
 
int main(void)
{
	int b;
	scanf("%d", &b);
 
	if (b == 1) printf("%lld\n", solve_1());
	else if (b == 2) printf("%lld\n", solve_2());
	else printf("%lld\n", solve_3());
}

Compilation message (stderr)

pairs.cpp: In function 'long long int solve_1()':
pairs.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &d, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x[i]);
   ~~~~~^~~~~~~~~~~~~
pairs.cpp: In function 'long long int solve_2()':
pairs.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &D, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i].first, &a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'long long int solve_3()':
pairs.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &D, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:297:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &b);
  ~~~~~^~~~~~~~~~

• 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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10