Submission #905242

#	Time	Username	Problem	Language	Result	Execution time	Memory
905242		rainboy	Posters on the wall (CPSPC17_posters)	C11	100 / 100	583 ms	146924 KiB

Main

#include <stdio.h>

#define N	50000
#define LN	17	/* LN = ceil(log2(N * 2)) */
#define N_	(N * 4 * (LN + 1) + 1)

typedef unsigned long long ull;

unsigned int Z = 12345;

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

int xx[N * 2], yy[N * 2], ii[N * 2], jj[N * 2], n;

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_] : ii[j] - i_;

			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 ll[N_], rr[N_]; ull aa[N_], bb[N_], cc[N_], dd[N_];

int update(int t, int l, int r, int i, ull a, ull b, ull c, ull d) {
	static int _ = 1;
	int t_ = _++;

	ll[t_] = ll[t], rr[t_] = rr[t], aa[t_] = aa[t] + a, bb[t_] = bb[t] + b, cc[t_] = cc[t] + c, dd[t_] = dd[t] + d;
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t_], l, m, i, a, b, c, d);
		else
			rr[t_] = update(rr[t_], m, r, i, a, b, c, d);
	}
	return t_;
}

ull a_, b_, c_, d_;

void query(int t, int l, int r, int i) {
	int m;

	if (t == 0 || l >= i)
		return;
	if (r <= i) {
		a_ += aa[t], b_ += bb[t], c_ += cc[t], d_ += dd[t];
		return;
	}
	m = (l + r) / 2;
	query(ll[t], l, m, i), query(rr[t], m, r, i);
}

int search_x(int x) {
	int lower = -1, upper = n * 2;

	while (upper - lower > 1) {
		int j = (lower + upper) / 2;

		if (xx[jj[j]] <= x)
			lower = j;
		else
			upper = j;
	}
	return upper;
}

int search_y(int y) {
	int lower = -1, upper = n * 2;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2;

		if (yy[ii[i]] <= y)
			lower = i;
		else
			upper = i;
	}
	return upper;
}

int tt[N * 2 + 1];

ull query_(int i, int j, int x, int y) {
	a_ = 0, b_ = 0, c_ = 0, d_ = 0, query(tt[i], 0, n * 2, j);
	return (a_ * x + b_) * y + (c_ * x + d_);
}

int main() {
	static int idx[N * 2];
	int q, md, tmp, i, i_, j, t;
	ull ans;

	scanf("%*d%*d%d%d%d", &n, &q, &md);
	for (i = 0; i < n * 2; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++) {
		if (xx[i << 1 | 0] > xx[i << 1 | 1])
			tmp = xx[i << 1 | 0], xx[i << 1 | 0] = xx[i << 1 | 1], xx[i << 1 | 1] = tmp;
		if (yy[i << 1 | 0] > yy[i << 1 | 1])
			tmp = yy[i << 1 | 0], yy[i << 1 | 0] = yy[i << 1 | 1], yy[i << 1 | 1] = tmp;
	}
	for (j = 0; j < n * 2; j++)
		jj[j] = j;
	ww = xx, sort(jj, 0, n * 2);
	for (j = 0; j < n * 2; j++)
		idx[jj[j]] = j;
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	ww = yy, sort(ii, 0, n * 2);
	for (i = 0, t = 0; i < n * 2; i++) {
		i_ = ii[i];
		t = update(t, 0, n * 2, idx[i_], 1, -xx[i_], -yy[i_], (ull) xx[i_] * yy[i_]);
		t = update(t, 0, n * 2, idx[i_ ^ 1], -1, xx[i_ ^ 1], yy[i_], (ull) -xx[i_ ^ 1] * yy[i_]);
		tt[i + 1] = t;
	}
	ans = 0;
	while (q--) {
		int x1, y1, x2, y2, w, i1, i2, j1, j2;

		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w), w = w * (ans % md) % md;
		x1 = (x1 + w) % md, y1 = (y1 + w) % md, x2 = (x2 + w) % md, y2 = (y2 + w) % md;
		if (x1 > x2)
			tmp = x1, x1 = x2, x2 = tmp;
		if (y1 > y2)
			tmp = y1, y1 = y2, y2 = tmp;
		i1 = search_y(y1), i2 = search_y(y2), j1 = search_x(x1), j2 = search_x(x2);
		printf("%llu\n", ans = query_(i2, j2, x2, y2) - query_(i2, j1, x1, y2) - query_(i1, j2, x2, y1) + query_(i1, j1, x1, y1));
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:114:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  scanf("%*d%*d%d%d%d", &n, &q, &md);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:116:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:141:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w), w = w * (ans % md) % md;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10