Submission #544755

#	Time	Username	Problem	Language	Result	Execution time	Memory
544755		rainboy	Mixture (BOI20_mixture)	C11	100 / 100	197 ms	29448 KiB

Mixture

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

#define N	100000
#define M	200000
#define MD	0x7fffffff

unsigned int Z = 12345, X = 12345;

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

long long abs_(long long x) { return x > 0 ? x : -x; }

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

long long *ox[M], *oy[M]; int *oc[M], oo[M];

int hash(long long x, long long y) {
	return ((x % MD * X % MD + y) % MD + MD) % M;
}

void ht_add(long long x, long long y, int c) {
	int h = hash(x, y), o;

	for (o = 0; o < oo[h]; o++)
		if (ox[h][o] == x && oy[h][o] == y) {
			oc[h][o] += c;
			return;
		}
	o = oo[h]++;
	if (o >= 2 && (o & o - 1) == 0) {
		ox[h] = (long long *) realloc(ox[h], o * 2 * sizeof *ox[h]);
		oy[h] = (long long *) realloc(oy[h], o * 2 * sizeof *oy[h]);
		oc[h] = (int *) realloc(oc[h], o * 2 * sizeof *oc[h]);
	}
	ox[h][o] = x, oy[h][o] = y, oc[h][o] = c;
}

int ht_get(long long x, long long y) {
	int h = hash(x, y), o;

	for (o = 0; o < oo[h]; o++)
		if (ox[h][o] == x && oy[h][o] == y)
			return oc[h][o];
	return 0;
}

long long xx[N], yy[N];

double cross(int i, int j) {
	return (double) xx[i] * yy[j] - (double) xx[j] * yy[i];
}

int cmp(int i, int j) {
	int sign_i = xx[i] < 0 || xx[i] == 0 && yy[i] < 0, sign_j = xx[j] < 0 || xx[j] == 0 && yy[j] < 0;
	double c = cross(i, j);

	return sign_i != sign_j ? sign_i - sign_j : (c != 0 ? (c < 0 ? -1 : 1) : i - j);
}

int bad(int i, int j) {
	double c = cross(i, j);

	return c > 0 || c == 0 && i > j;
}

int zz[1 + N], ll[1 + N], rr[1 + N], kk[1 + N], u_, l_, r_;

int node(int k) {
	static int _ = 1;

	zz[_] = rand_();
	kk[_] = k;
	return _++;
}

void split(int u, int k) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = cmp(kk[u], k);
	if (c < 0) {
		split(rr[u], k);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], k);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

int kbad;

void tr_add(int i) {
	if (u_ == 0)
		u_ = node(i);
	else {
		int l, r;

		split(u_, i);
		l = kk[l_ ? last(l_) : last(r_)], r = kk[r_ ? first(r_) : first(l_)];
		kbad += bad(l, i) + bad(i, r) - bad(l, r);
		u_ = merge(merge(l_, node(i)), r_);
	}
}

void tr_remove(int i) {
	if (ll[u_] == 0 && rr[u_] == 0)
		u_ = 0;
	else {
		int l, r;

		split(u_, i);
		l = kk[l_ ? last(l_) : last(r_)], r = kk[r_ ? first(r_) : first(l_)];
		kbad -= bad(l, i) + bad(i, r) - bad(l, r);
		u_ = merge(l_, r_);
	}
}

int main() {
	int n, q, h, x0, y0, z0, w0, k1;
	long long k2;

	scanf("%d%d%d%d", &x0, &y0, &z0, &q), w0 = x0 + y0 + z0;
	for (h = 0; h < M; h++) {
		ox[h] = (long long *) malloc(2 * sizeof *ox[h]);
		oy[h] = (long long *) malloc(2 * sizeof *oy[h]);
		oc[h] = (int *) malloc(2 * sizeof *oc[h]);
	}
	n = 0, k1 = 0, k2 = 0, kbad = 0;
	while (q--) {
		static char s[2];

		scanf("%s", s);
		if (s[0] == 'A') {
			int x, y, z, w;
			long long x_, y_, d;

			scanf("%d%d%d", &x, &y, &z), w = x + y + z;
			x_ = (long long) x * w0 - (long long) x0 * w;
			y_ = (long long) y * w0 - (long long) y0 * w;
			d = gcd(abs_(x_), abs_(y_));
			if (d != 0)
				x_ /= d, y_ /= d;
			xx[n] = x_, yy[n] = y_, n++;
			if (xx[n - 1] == 0 && yy[n - 1] == 0)
				k1++;
			else {
				k2 += ht_get(-x_, -y_);
				ht_add(x_, y_, 1);
				tr_add(n - 1);
			}
		} else {
			int i;

			scanf("%d", &i), i--;
			if (xx[i] == 0 && yy[i] == 0)
				k1--;
			else {
				ht_add(xx[i], yy[i], -1);
				k2 -= ht_get(-xx[i], -yy[i]);
				tr_remove(i);
			}
		}
		printf(k1 > 0 ? "1\n" : (k2 > 0 ? "2\n" : ((ll[u_] || rr[u_]) && kbad == 0 ? "3\n" : "0\n")));
	}
	return 0;
}

Compilation message (stderr)

Mixture.c: In function 'ht_add':
Mixture.c:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Mixture.c: In function 'cmp':
Mixture.c:59:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |  int sign_i = xx[i] < 0 || xx[i] == 0 && yy[i] < 0, sign_j = xx[j] < 0 || xx[j] == 0 && yy[j] < 0;
      |                            ~~~~~~~~~~~^~~~~~~~~~~~
Mixture.c:59:86: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |  int sign_i = xx[i] < 0 || xx[i] == 0 && yy[i] < 0, sign_j = xx[j] < 0 || xx[j] == 0 && yy[j] < 0;
      |                                                                           ~~~~~~~~~~~^~~~~~~~~~~~
Mixture.c: In function 'bad':
Mixture.c:68:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |  return c > 0 || c == 0 && i > j;
      |                  ~~~~~~~^~~~~~~~
Mixture.c: In function 'main':
Mixture.c:155:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  scanf("%d%d%d%d", &x0, &y0, &z0, &q), w0 = x0 + y0 + z0;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.c:165:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
Mixture.c:170:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |    scanf("%d%d%d", &x, &y, &z), w = x + y + z;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.c:187:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40