Submission #533238

#	Time	Username	Problem	Language	Result	Execution time	Memory
533238		lunchbox	New Home (APIO18_new_home)	C11	100 / 100	2727 ms	72604 KiB

new_home

#include <stdio.h>
#include <sys/time.h>

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

#define N	300000
#define K	300000
#define Q	300000
#define M	(300000 + 2)
#define M_	(1 << 19)	/* M_ = pow2(ceil(log2(M))) */	
#define T	(K * 3 + N * 6)
#define INF	0x3f3f3f3f

unsigned int X;
 
void srand_() {
	struct timeval tv;
 
	gettimeofday(&tv, NULL);
	X = tv.tv_sec ^ tv.tv_usec | 1;
}
 
int rand_() {
	return (X *= 3) >> 1;
}

int *vv;

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h_ = hh[l + rand_() % (r - l)], tmp;
 
		while (j < k) {
			int c = vv[hh[j]] - vv[h_];
 
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int zz[T + 1], ll[T + 1], rr[T + 1], kk[T + 1], cnt[T + 1];
 
int node(int key) {
	static int _ = 1;
 
	zz[_] = rand_();
	kk[_] = key;
	return _++;
}
 
int l_, r_;

int i_;

void split_(int i, int key) {
	if (i == 0) {
		i_ = l_ = r_ = 0;
		return;
	}
	if (kk[i] < key) {
		split_(rr[i], key);
		rr[i] = l_, l_ = i;
	} else if (kk[i] > key) {
		split_(ll[i], key);
		ll[i] = r_, r_ = i;
	} else {
		i_ = i, l_ = ll[i], r_ = rr[i];
		ll[i] = rr[i] = 0;
	}
}

int merge(int i, int j) {
	if (i == 0)
		return j;
	if (j == 0)
		return i;
	if (zz[i] < zz[j]) {
		rr[i] = merge(rr[i], j);
		return i;
	} else {
		ll[j] = merge(i, ll[j]);
		return j;
	}
}

void split(int i, int key) {
	split_(i, key);
	r_ = merge(i_, r_);
}

int first(int i) {
	while (ll[i] != 0)
		i = ll[i];
	return i;
}

int last(int i) {
	while (rr[i] != 0)
		i = rr[i];
	return i;
}

int add(int i, int key) {
	split_(i, key);
	if (i_ == 0)
		i_ = node(key);
	cnt[i_]++;
	return merge(l_, merge(i_, r_));
}

int erase(int i, int key) {
	split_(i, key);
	if (--cnt[i_] == 0)
		i_ = 0;
	return merge(l_, merge(i_, r_));
}


int aa[M], m;

int ii(int a) {
	int lower = 0, upper = m - 1;

	while (lower < upper) {
		int t = (lower + upper) / 2;

		if (aa[t] < a)
			lower = t + 1;
		else if (aa[t] > a)
			upper = t - 1;
		else
			lower = upper = t;
	}
	return lower;
}

int st[M_ * 2], mx[M_ * 2], m_;

void build(int *aa, int m) {
	int i;

	m_ = 1;
	while (m_ < m)
		m_ <<= 1;
	for (i = 0; i < m_; i++) {
		st[m_ + i] = INF;
		mx[m_ + i] = i < m ? aa[i] : -INF;
	}
	for (i = m_ - 1; i > 0; i--) {
		st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
		mx[i]  = max(mx[i << 1 | 0], mx[i << 1 | 1]);
	}
}

void update(int i, int x) {
	st[i += m_] = x;
	while (i > 1) {
		i >>= 1;
		st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
	}
}

int tr_[M];

void update_(int l, int r, int t) {
	r = ii(r);
	if (t == +1)
		tr_[r] = add(tr_[r], l);
	else
		tr_[r] = erase(tr_[r], l);
	update(r, tr_[r] == 0 ? INF : kk[first(tr_[r])]);
}

int query(int x) {
	int i = 1, v = INF;

	while (i < m_) {
		if (x > mx[i << 1 | 0]) {
			i = i << 1 | 1;
			continue;
		}
		if (mx[i << 1 | 0] + 1 + min(st[i << 1 | 1], v) <= 2 * x)
			i = i << 1 | 1;
		else {
			v = min(v, st[i << 1 | 1]);
			i = i << 1 | 0;
		}
	}
	return min(2 * x - min(v, st[i]), mx[i]) - x;
}

int main() {
	static int xx[N], gg[N], ll[N], rr[N], yy[Q], tt[Q], ans[Q];
	static int hh[M], hh0[N], hh1[N], hh2[Q];
	static int tr[K], cnt_[K];
	int n, k, q, i, i0, i1, i2, active;

	srand_();
	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n; i++) {
		scanf("%d%d%d%d", &xx[i], &gg[i], &ll[i], &rr[i]), gg[i]--;
		hh[i] = i;
		hh0[i] = i;
		hh1[i] = i;
	}
	for (i = 0; i < q; i++) {
		scanf("%d%d", &yy[i], &tt[i]);
		hh2[i] = i;
	}
	vv = xx, sort(hh, 0, n);
	vv = ll, sort(hh0, 0, n);
	vv = rr, sort(hh1, 0, n);
	vv = tt, sort(hh2, 0, q);
	for (i = 0; i < k; i++) {
		tr[i] = add(tr[i], -INF);
		tr[i] = add(tr[i], +INF);
		update_(-INF, +INF, +1);
	}
	m = 0;
	aa[m++] = -INF;
	for (i = 0; i < n; i++)
		if (i == 0 || xx[hh[i]] != xx[hh[i - 1]])
			aa[m++] = xx[hh[i]];
	aa[m++] = +INF;
	build(aa, m);
	i0 = i1 = i2 = 0;
	active = 0;
	for (i = 0; i < q; i++) {
		int h, g, x, l, r, prev, next;

		while (i0 < n && ll[hh0[i0]] <= tt[hh2[i]]) {
			h = hh0[i0], g = gg[h], x = xx[h];
			split(tr[g], x);
			l = l_, r = r_;
			prev = last(l);
			next = first(r);
			update_(kk[prev], kk[next], -1);
			update_(kk[prev], x, +1);
			update_(x, kk[next], +1);
			tr[g] = add(merge(l, r), x);
			if (++cnt_[g] == 1)
				active++;
			i0++;
		}
		while (i1 < n && rr[hh1[i1]] < tt[hh2[i]]) {
			h = hh1[i1], g = gg[h], x = xx[h];
			tr[g] = erase(tr[g], x);
			split(tr[g], x);
			l = l_, r = r_;
			prev = last(l);
			next = first(r);
			update_(kk[prev], kk[next], +1);
			update_(kk[prev], x, -1);
			update_(x, kk[next], -1);
			tr[g] = merge(l, r);
			if (--cnt_[g] == 0)
				active--;
			i1++;
		}
		ans[hh2[i]] = active == k ? query(yy[hh2[i]]) : -1;
	}
	for (i = 0; i < q; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

new_home.c: In function 'srand_':
new_home.c:21:16: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   21 |  X = tv.tv_sec ^ tv.tv_usec | 1;
      |      ~~~~~~~~~~^~~~~~~~~~~~
new_home.c: In function 'main':
new_home.c:210:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:212:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |   scanf("%d%d%d%d", &xx[i], &gg[i], &ll[i], &rr[i]), gg[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:218:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  218 |   scanf("%d%d", &yy[i], &tt[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20