Submission #447990

#	Time	Username	Problem	Language	Result	Execution time	Memory
447990		rainboy	Pairs (IOI07_pairs)	C11	100 / 100	301 ms	25112 KiB

pairs

#include <stdio.h>
#include <stdlib.h>

#define N	100000
#define M2	150000
#define M3	225

int compare1(const void *a, const void *b) {
	int ia = *(int *) a;
	int ib = *(int *) b;

	return ia - ib;
}

long long solve1() {
	static int xx[N];
	int n, d, m, i, j;
	long long cnt = 0;

	scanf("%d%d%d", &n, &d, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &xx[i]);
	qsort(xx, n, sizeof *xx, compare1);
	for (i = 0, j = 0; j < n; j++) {
		while (xx[j] - xx[i] > d)
			i++;
		cnt += j - i;
	}
	return cnt;
}

struct P {
	int x, y;
} pp[N];

int compare2(const void *p_, const void *q_) {
	struct P *p = (struct P *) p_;
	struct P *q = (struct P *) q_;

	return p->x - q->x;
}

int tt[M2 + 1];

void update(int i, int x) {
	while (i <= M2) {
		tt[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int cnt = 0;

	while (i >= 0) {
		cnt += tt[i];
		i &= i + 1;
		i--;
	}
	return cnt;
}

int query_(int l, int r) {
	if (r > M2)
		r = M2;
	return query(r) - query(l - 1);
}

long long solve2() {
	int n, d, m, i, j;
	long long cnt = 0;

	scanf("%d%d%d", &n, &d, &m);
	for (i = 0; i < n; i++) {
		struct P *p = &pp[i];
		int x, y;

		scanf("%d%d", &x, &y);
		p->x = x + y;
		p->y = x + m - y;
	}
	qsort(pp, n, sizeof *pp, compare2);
	for (i = 0, j = 0; j < n; j++) {
		while (pp[j].x - pp[i].x > d)
			update(pp[i++].y, -1);
		cnt += query_(pp[j].y - d, pp[j].y + d);
		update(pp[j].y, 1);
	}
	return cnt;
}

struct Q {
	int w, x, y, z;
} qq[N];

int compare3(const void *p_, const void *q_) {
	struct Q *p = (struct Q *) p_;
	struct Q *q = (struct Q *) q_;

	return p->w - q->w;
}

int tt3[M3 + 1][M3 + 1][M3 + 1];

void update3(struct Q *q, int x) {
	int i = q->x;

	while (i <= M3) {
		int j = q->y;

		while (j <= M3) {
			int k = q->z;

			while (k <= M3) {
				tt3[i][j][k] += x;
				k |= k + 1;
			}
			j |= j + 1;
		}
		i |= i + 1;
	}
}

int query3(int i_, int j_, int k_) {
	int cnt = 0;
	int i = i_;

	while (i >= 0) {
		int j = j_;

		while (j >= 0) {
			int k = k_;

			while (k >= 0) {
				cnt += tt3[i][j][k];
				k &= k + 1;
				k--;
			}
			j &= j + 1;
			j--;
		}
		i &= i + 1;
		i--;
	}
	return cnt;
}

int query3_(struct Q *q, int d) {
	int x1 = q->x - d - 1;
	int x2 = q->x + d;
	int y1 = q->y - d - 1;
	int y2 = q->y + d;
	int z1 = q->z - d - 1;
	int z2 = q->z + d;
	int cnt;

	if (x2 > M3)
		x2 = M3;
	if (y2 > M3)
		y2 = M3;
	if (z2 > M3)
		z2 = M3;
	cnt = query3(x2, y2, z2);
	cnt -= query3(x1, y2, z2);
	cnt -= query3(x2, y1, z2);
	cnt -= query3(x2, y2, z1);
	cnt += query3(x1, y1, z2);
	cnt += query3(x2, y1, z1);
	cnt += query3(x1, y2, z1);
	cnt -= query3(x1, y1, z1);
	return cnt;
}

long long solve3() {
	int n, d, m, i, j;
	long long cnt = 0;

	scanf("%d%d%d", &n, &d, &m);
	for (i = 0; i < n; i++) {
		struct Q *q = &qq[i];
		int x, y, z;

		scanf("%d%d%d", &x, &y, &z);
		q->w = x + y + z;
		q->x = x + m - y + z;
		q->y = x + y + m - z;
		q->z = x + m - y + m - z;
	}
	qsort(qq, n, sizeof *qq, compare3);
	for (i = 0, j = 0; j < n; j++) {
		while (qq[j].w - qq[i].w > d)
			update3(&qq[i++], -1);
		cnt += query3_(&qq[j], d);
		update3(&qq[j], 1);
	}
	return cnt;
}

int main() {
	long long ans;
	int b;

	scanf("%d", &b);
	if (b == 1)
		ans = solve1();
	else if (b == 2)
		ans = solve2();
	else
		ans = solve3();
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

pairs.c: In function 'solve1':
pairs.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d%d%d", &n, &d, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.c:22:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~
pairs.c: In function 'solve2':
pairs.c:73:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d%d", &n, &d, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d%d", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~
pairs.c: In function 'solve3':
pairs.c:178:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |  scanf("%d%d%d", &n, &d, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.c:183:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |   scanf("%d%d%d", &x, &y, &z);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.c: In function 'main':
pairs.c:203:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |  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: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10