oj.uz

Submission #485821

# Submission time Handle Problem Language Result Execution time Memory
485821 2021-11-09T13:17:03 Z rainboy Krave (COI14_krave) C
100 / 100
 450 ms 25812 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 6596 KB Output is correct
2 Correct 125 ms 10108 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 6596 KB Output is correct
2 Correct 150 ms 10180 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 6544 KB Output is correct
2 Correct 269 ms 17132 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 7248 KB Output is correct
2 Correct 203 ms 17856 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 13008 KB Output is correct
2 Correct 233 ms 19280 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 12628 KB Output is correct
2 Correct 250 ms 14268 KB Output is correct
3 Correct 177 ms 12552 KB Output is correct
4 Correct 226 ms 20256 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 13096 KB Output is correct
2 Correct 263 ms 15852 KB Output is correct
3 Correct 218 ms 14328 KB Output is correct
4 Correct 307 ms 25676 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 13264 KB Output is correct
2 Correct 188 ms 12648 KB Output is correct
3 Correct 239 ms 14356 KB Output is correct
4 Correct 294 ms 25812 KB Output is correct