Submission #392855

#	Time	Username	Problem	Language	Result	Execution time	Memory
392855		rainboy	Topovi (COCI15_topovi)	C11	120 / 120	343 ms	19652 KiB

topovi

#include <stdio.h>
#include <string.h>

#define N	100000
#define Q	100000
#define M	(N + Q * 2)
#define M_	(M * 2 + 1)

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int xx[M], yy[M], ww[M_];

int compare_x(int i, int j) { return xx[i] - xx[j]; }
int compare_y(int i, int j) { return yy[i] - yy[j]; }
int compare_xy(int i, int j) { return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j]; }
int compare_w(int i, int j) { return ww[i] - ww[j]; }

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

void compress(int *xx, int n) {
	static int ii[M_];
	int i, x;

	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	for (i = 0, x = 0; i < n; i++)
		xx[ii[i]] = i + 1 == n || compare(ii[i + 1], ii[i]) != 0 ? x++ : x;
}

int main() {
	static int ii_[M], aa[N], aa_[M], uu[M], vv[M], kk[M_], ll[M_];
	int s, n, q, m, i;
	long long ans;

	scanf("%d%d%d", &s, &n, &q), m = n + q * 2;
	for (i = 0; i < n; i++)
		scanf("%d%d%d", &xx[i], &yy[i], &aa[i]);
	for (i = 0; i < q * 2; i++)
		scanf("%d%d", &xx[n + i], &yy[n + i]);
	compare = compare_x, compress(xx, m);
	compare = compare_y, compress(yy, m);
	compare = compare_xy, compress(ii_, m);
	for (i = 0; i < n; i++) {
		int i_ = ii_[i];

		aa_[i_] = aa[i];
		ww[i << 1 | 0] = uu[xx[i]] ^= aa_[i_], ww[i << 1 | 1] = vv[yy[i]] ^= aa_[i_];
	}
	for (i = 0; i < q * 2; i++) {
		int i_ = ii_[n + i];

		if ((i & 1) == 1)
			aa_[i_] = aa_[ii_[n + (i ^ 1)]];
		ww[n + i << 1 | 0] = uu[xx[n + i]] ^= aa_[i_], ww[n + i << 1 | 1] = vv[yy[n + i]] ^= aa_[i_];
	}
	compare = compare_w, compress(ww, m * 2 + 1);
	kk[0] = ll[0] = s;
	memset(uu, 0, m * sizeof *uu), memset(vv, 0, m * sizeof *vv);
	ans = 0;
	for (i = 0; i < m; i++) {
		int x = xx[i], y = yy[i];

		ans += ll[uu[x]], kk[uu[x]]--, uu[x] = ww[i << 1 | 0], ans -= ll[uu[x]], kk[uu[x]]++;
		ans += kk[vv[y]], ll[vv[y]]--, vv[y] = ww[i << 1 | 1], ans -= kk[vv[y]], ll[vv[y]]++;
		if (i >= n && (i - n & 1) == 1)
			printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

topovi.c: In function 'main':
topovi.c:81:8: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   81 |   ww[n + i << 1 | 0] = uu[xx[n + i]] ^= aa_[i_], ww[n + i << 1 | 1] = vv[yy[n + i]] ^= aa_[i_];
      |      ~~^~~
topovi.c:81:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   81 |   ww[n + i << 1 | 0] = uu[xx[n + i]] ^= aa_[i_], ww[n + i << 1 | 1] = vv[yy[n + i]] ^= aa_[i_];
      |                                                     ~~^~~
topovi.c:92:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   92 |   if (i >= n && (i - n & 1) == 1)
      |                  ~~^~~
topovi.c:62:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%d%d%d", &s, &n, &q), m = n + q * 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
topovi.c:64:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d%d%d", &xx[i], &yy[i], &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
topovi.c:66:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   66 |   scanf("%d%d", &xx[n + i], &yy[n + i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120