Submission #730938

#	Time	Username	Problem	Language	Result	Execution time	Memory
730938		rainboy	Monkey and Apple-trees (IZhO12_apple)	C11	100 / 100	48 ms	4096 KiB

apple

#include <stdio.h>

#define N	100000

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

unsigned int X = 12345;

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

int zz[N + 1], ll[N + 1], rr[N + 1], xx[N + 1], yy[N + 1], sz[N + 1], u_, l_, r_;

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

	zz[_] = rand_();
	xx[_] = x, yy[_] = y, sz[_] = yy[_] - xx[_];
	return _++;
}

void pul(int u) {
	sz[u] = sz[ll[u]] + (yy[u] - xx[u]) + sz[rr[u]];
}

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

void split_y(int u, int y) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (yy[u] < y) {
		split_y(rr[u], y);
		rr[u] = l_, l_ = u;
	} else {
		split_y(ll[u], y);
		ll[u] = r_, r_ = u;
	}
	pul(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), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(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 main() {
	int n, c;

	scanf("%d", &n);
	c = 0;
	while (n--) {
		int t, x, y, l, u, r;

		scanf("%d%d%d", &t, &x, &y), x += c, y += c, x--;
		split_y(u_, x), l = l_;
		split_x(r_, y), u = l_, r = r_;
		if (t == 2)
			u = u == 0 ? node(x, y) : node(min(x, xx[first(u)]), max(y, yy[last(u)]));
		else
			printf("%d\n", c = u == 0 ? 0 : sz[u] - max(x - xx[first(u)], 0) - max(yy[last(u)] - y, 0));
		u_ = merge(merge(l, u), r);
	}
	return 0;
}

Compilation message (stderr)

apple.c: In function 'main':
apple.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
apple.c:88:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d%d%d", &t, &x, &y), x += c, y += c, x--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100