Submission #485821

#	Time	Username	Problem	Language	Result	Execution time	Memory
485821		rainboy	Krave (COI14_krave)	C11	100 / 100	450 ms	25812 KiB

krave

#include <stdio.h>

#define Q	100000
#define L	17	/* L = ceil(log2(N)) */
#define N_	(1 << L)
#define N1	(1 + (Q + 4) * (L * 2 + 1))
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int Z = 12345;

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

int zz[N1], ll[N1], rr[N1], xx[N1], l_, r_;

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

	zz[_] = rand_();
	xx[_] = x;
	return _++;
}

void split(int u, int x) {
	if (u == 0) {
		l_ = r_ = 0;
		return;
	}
	if (xx[u] < x) {
		split(rr[u], x);
		rr[u] = l_, l_ = u;
	} else {
		split(ll[u], x);
		ll[u] = r_, r_ = u;
	}
}

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 tr_add(int u, int x) {
	split(u, x);
	return merge(merge(l_, node(x)), r_);
}

int tr_floor(int u, int x) {
	int x_ = -INF;

	while (u)
		if (xx[u] <= x)
			x_ = xx[u], u = rr[u];
		else
			u = ll[u];
	return x_;
}

int tr_ceil(int u, int x) {
	int x_ = INF;

	while (u)
		if (xx[u] >= x)
			x_ = xx[u], u = ll[u];
		else
			u = rr[u];
	return x_;
}

void update(int *st, int n_, int l, int r, int x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l] = tr_add(st[l], x), l++;
		if ((r & 1) == 0)
			st[r] = tr_add(st[r], x), r--;
	}
}

void query(int *st, int n_, int i, int x, int *xl_, int *xr_) {
	int xl = -INF, xr = INF;

	for (i += n_; i > 0; i >>= 1)
		xl = max(xl, tr_floor(st[i], x)), xr = min(xr, tr_ceil(st[i], x));
	*xl_ = xl, *xr_ = xr;
}

int main() {
	static int stx[N_ * 2], sty[N_ * 2];
	int n, n_, m, m_, q;

	scanf("%d%d", &n, &m);
	n_ = 1;
	while (n_ < n + 1)
		n_ <<= 1;
	m_ = 1;
	while (m_ < m + 1)
		m_ <<= 1;
	update(stx, m_, 0, m, 0), update(stx, m_, 0, m, n);
	update(sty, n_, 0, n, 0), update(sty, n_, 0, n, m);
	scanf("%d", &q);
	while (q--) {
		int x, xl, xr, y, yl, yr, d;
		long long a1, a2, tmp;

		scanf("%d%d%d", &x, &y, &d);
		query(stx, m_, y, x, &xl, &xr);
		query(sty, n_, x, y, &yl, &yr);
		if (d == 1) {
			a1 = (long long) (xr - xl) * (y - yl), a2 = (long long) (xr - xl) * (yr - y);
			update(sty, n_, xl, xr, y);
		} else {
			a1 = (long long) (yr - yl) * (x - xl), a2 = (long long) (yr - yl) * (xr - x);
			update(stx, m_, yl, yr, x);
		}
		if (a1 > a2)
			tmp = a1, a1 = a2, a2 = tmp;
		printf("%lld %lld\n", a1, a2);
	}
	return 0;
}

Compilation message (stderr)

krave.c: In function 'main':
krave.c:104:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
krave.c:113:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
krave.c:118:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%d%d%d", &x, &y, &d);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12