oj.uz

답안 #152962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152962 2019-09-10T18:53:01 Z luciocf Pairs (IOI07_pairs) C++14
100 / 100
 284 ms 4856 KB 
#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

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.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 636 KB Output is correct
2 Correct 20 ms 760 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 760 KB Output is correct
2 Correct 27 ms 784 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 632 KB Output is correct
2 Correct 27 ms 784 KB Output is correct
3 Correct 26 ms 760 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 4308 KB Output is correct
2 Correct 49 ms 4344 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 4216 KB Output is correct
2 Correct 61 ms 4228 KB Output is correct
3 Correct 64 ms 4232 KB Output is correct
4 Correct 62 ms 4216 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 4220 KB Output is correct
2 Correct 68 ms 4296 KB Output is correct
3 Correct 67 ms 4344 KB Output is correct
4 Correct 66 ms 4216 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2808 KB Output is correct
2 Correct 7 ms 2808 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 4088 KB Output is correct
2 Correct 211 ms 4728 KB Output is correct
3 Correct 209 ms 4584 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 3960 KB Output is correct
2 Correct 244 ms 4728 KB Output is correct
3 Correct 230 ms 4820 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 3944 KB Output is correct
2 Correct 245 ms 4856 KB Output is correct
3 Correct 235 ms 4856 KB Output is correct