oj.uz

Submission #447990

# Submission time Handle Problem Language Result Execution time Memory
447990 2021-07-28T11:51:54 Z rainboy Pairs (IOI07_pairs) C
100 / 100
 301 ms 25112 KB 
#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

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

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1356 KB Output is correct
2 Correct 23 ms 1436 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1860 KB Output is correct
2 Correct 27 ms 1904 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1904 KB Output is correct
2 Correct 28 ms 1932 KB Output is correct
3 Correct 29 ms 1868 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2320 KB Output is correct
2 Correct 34 ms 2324 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2512 KB Output is correct
2 Correct 40 ms 2612 KB Output is correct
3 Correct 39 ms 2612 KB Output is correct
4 Correct 41 ms 2608 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2888 KB Output is correct
2 Correct 45 ms 2924 KB Output is correct
3 Correct 42 ms 2884 KB Output is correct
4 Correct 42 ms 2960 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11852 KB Output is correct
2 Correct 7 ms 11852 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4028 KB Output is correct
2 Correct 118 ms 3908 KB Output is correct
3 Correct 84 ms 3908 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 18096 KB Output is correct
2 Correct 229 ms 17992 KB Output is correct
3 Correct 95 ms 17988 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 25112 KB Output is correct
2 Correct 256 ms 25092 KB Output is correct
3 Correct 109 ms 25112 KB Output is correct