Submission #673459

#	Time	Username	Problem	Language	Result	Execution time	Memory
673459		rainboy	Examination (JOI19_examination)	C11	100 / 100	1856 ms	48144 KiB

examination

#include <stdio.h>

#define N	100000
#define Q	100000
#define M	(N + Q)
#define H_	18	/* H_ = ceil(log2(M)) */
#define N1	(N * (H_ + 1) + 1)
#define N_	(1 << H_)

unsigned int X = 12345;

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

int xx[M], yy[M], zz[M];

int *ww;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = ww[ii[j]] != ww[i_] ? ww[ii[j]] - ww[i_] : i_ - ii[j];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int vv[N1], ll[N1], rr[N1], sz[N1], ii_[N1], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	vv[_] = rand_();
	sz[_] = 1;
	ii_[_] = i;
	return _++;
}

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

void split(int u, int i) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (yy[ii_[u]] < yy[i]) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (yy[ii_[u]] > yy[i]) {
		split(ll[u], i);
		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 (vv[u] < vv[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 u, int i) {
	split(u, i);
	return merge(merge(l_, node(i)), r_);
}

int tr_query(int u, int y) {
	int k = 0;

	while (u)
		if (yy[ii_[u]] >= y)
			k += sz[rr[u]] + 1, u = ll[u];
		else
			u = rr[u];
	return k;
}

int uu[N_ * 2], n_;

void update(int i, int i_) {
	for (i += n_; i > 0; i >>= 1)
		uu[i] = tr_add(uu[i], i_);
}

int query(int l, int y) {
	int r = n_ - 1, k = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1)
			k += tr_query(uu[l++], y);
	return k;
}

int main() {
	static int ii[M], ans[Q];
	int n, q, m, h, i, i_;

	scanf("%d%d", &n, &q), m = n + q;
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]), zz[i] = xx[i] + yy[i];
	for (h = 0; h < q; h++)
		scanf("%d%d%d", &xx[n + h], &yy[n + h], &zz[n + h]);
	for (i = 0; i < m; i++)
		ii[i] = i;
	ww = xx, sort(ii, 0, m);
	for (i = 0; i < m; i++)
		xx[ii[i]] = i;
	ww = yy, sort(ii, 0, m);
	for (i = 0; i < m; i++)
		yy[ii[i]] = i;
	ww = zz, sort(ii, 0, m);
	n_ = 1;
	while (n_ < m)
		n_ <<= 1;
	for (i = m - 1; i >= 0; i--) {
		i_ = ii[i];
		if (i_ < n)
			update(xx[i_], i_);
		else
			ans[i_ - n] = query(xx[i_], yy[i_]);
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

examination.c: In function 'main':
examination.c:125:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  scanf("%d%d", &n, &q), m = n + q;
      |  ^~~~~~~~~~~~~~~~~~~~~
examination.c:127:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |   scanf("%d%d", &xx[i], &yy[i]), zz[i] = xx[i] + yy[i];
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.c:129:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   scanf("%d%d%d", &xx[n + h], &yy[n + h], &zz[n + h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57