제출 #486379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486379		rainboy	Ruka (COI15_ruka)	C11	100 / 100	550 ms	10300 KiB

ruka

#include <stdio.h>

#define N	100000
#define Q	300000
#define N_	(1 + (N * 2 + Q * 4) * 2)

unsigned int Z = 12345;

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

int zz[N_], ll[N_], rr[N_], xx[N_], cc[N_], sum[N_], u_, l_, r_;

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

	zz[_] = rand_();
	xx[_] = x, sum[_] = cc[_] = c;
	return _++;
}

void pul(int u) {
	sum[u] = cc[u] + sum[ll[u]] + sum[rr[u]];
}

void split(int u, int x) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (xx[u] < x) {
		split(rr[u], x);
		rr[u] = l_, l_ = u;
	} else if (xx[u] > x) {
		split(ll[u], x);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	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 tr_add(int t, int x, int c) {
	split(t, x);
	if (u_ == 0)
		u_ = node(x, 0);
	if ((cc[u_] += c) == 0)
		u_ = 0;
	pul(u_);
	t = merge(merge(l_, u_), r_);
	return t;
}

int add(int t, int x1, int x2, int c) {
	if (x1 != x2 && c != 0) {
		int tmp;

		if (x1 > x2)
			tmp = x1, x1 = x2, x2 = tmp;
		t = tr_add(t, x1, c), t = tr_add(t, x2, -c);
	}
	return t;
}

int query(int t, int x) {
	int c = 0;

	while (t)
		if (xx[t] <= x)
			c += sum[ll[t]] + cc[t], t = rr[t];
		else
			t = ll[t];
	return c;
}

int main() {
	static int xx[N], yy[N], xxp[N + 1], yyp[N + 1], xxq[N + 1], yyq[N + 1];
	int n, m, i, x, y, tx, ty, p, q;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	scanf("%d", &m);
	x = 0, y = 0, tx = 0, ty = 0;
	for (i = n - 1; i >= 0; i--) {
		xxq[i] = x, yyq[i] = y, x += xx[i], y += yy[i];
		tx = add(tx, xxq[i], xxq[i] + xx[i], 1), ty = add(ty, yyq[i], yyq[i] + yy[i], 1);
	}
	x++, y++;
	xxp[0] = 1, yyp[0] = 1;
	i = 0, p = 0, q = query(tx, x) + query(ty, y);
	while (m--) {
		static char s[2];

		scanf("%s", s);
		if (s[0] == 'B') {
			if (i > 0) {
				i--;
				if ((xxp[i] > 0) != (xxp[i] + xx[i] > 0))
					p--;
				if ((yyp[i] > 0) != (yyp[i] + yy[i] > 0))
					p--;
				xxq[i] = xxq[i + 1] + xx[i + 1], yyq[i] = yyq[i + 1] + yy[i + 1];
				tx = add(tx, xxq[i], xxq[i] + xx[i], 1), ty = add(ty, yyq[i], yyq[i] + yy[i], 1);
				q = query(tx, x) + query(ty, y);
			}
		} else if (s[0] == 'F') {
			if (i + 1 < n) {
				tx = add(tx, xxq[i], xxq[i] + xx[i], -1), ty = add(ty, yyq[i], yyq[i] + yy[i], -1);
				if ((xxp[i] > 0) != (xxp[i] + xx[i] > 0))
					p++;
				if ((yyp[i] > 0) != (yyp[i] + yy[i] > 0))
					p++;
				i++;
				xxp[i] = xxp[i - 1] + xx[i - 1], yyp[i] = yyp[i - 1] + yy[i - 1];
				q = query(tx, x) + query(ty, y);
			}
		} else if (s[0] == 'C') {
			int x_, y_;

			scanf("%d%d", &x_, &y_);
			tx = add(tx, xxq[i], xxq[i] + xx[i], -1), ty = add(ty, yyq[i], yyq[i] + yy[i], -1);
			x += x_ - xx[i], y += y_ - yy[i], xx[i] = x_, yy[i] = y_;
			tx = add(tx, xxq[i], xxq[i] + xx[i], 1), ty = add(ty, yyq[i], yyq[i] + yy[i], 1);
			q = query(tx, x) + query(ty, y);
		} else
			printf("%d\n", p + q);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ruka.c: In function 'main':
ruka.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
ruka.c:98:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.c:99:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
ruka.c:111:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
ruka.c:137:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |    scanf("%d%d", &x_, &y_);
      |    ^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56