oj.uz

답안 #486379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486379 2021-11-11T13:21:45 Z rainboy Ruka (COI15_ruka) C
100 / 100
 550 ms 10300 KB 
#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;
}

Compilation message

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 167 ms 2344 KB Output is correct
6 Correct 147 ms 3316 KB Output is correct
7 Correct 148 ms 2688 KB Output is correct
8 Correct 149 ms 2636 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 167 ms 2344 KB Output is correct
6 Correct 147 ms 3316 KB Output is correct
7 Correct 148 ms 2688 KB Output is correct
8 Correct 149 ms 2636 KB Output is correct
9 Correct 470 ms 10300 KB Output is correct
10 Correct 550 ms 10188 KB Output is correct
11 Correct 401 ms 8072 KB Output is correct
12 Correct 462 ms 10272 KB Output is correct