oj.uz

Submission #905242

# Submission time Handle Problem Language Result Execution time Memory
905242 2024-01-12T21:03:12 Z rainboy Posters on the wall (CPSPC17_posters) C
100 / 100
 583 ms 146924 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3164 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3316 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3164 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3316 KB Output is correct
4 Correct 28 ms 19248 KB Output is correct
5 Correct 23 ms 19292 KB Output is correct
6 Correct 24 ms 19028 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3164 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3316 KB Output is correct
4 Correct 28 ms 19248 KB Output is correct
5 Correct 23 ms 19292 KB Output is correct
6 Correct 24 ms 19028 KB Output is correct
7 Correct 205 ms 144212 KB Output is correct
8 Correct 571 ms 144720 KB Output is correct
9 Correct 341 ms 145048 KB Output is correct
10 Correct 468 ms 144640 KB Output is correct
11 Correct 418 ms 144824 KB Output is correct
12 Correct 365 ms 144724 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3164 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3316 KB Output is correct
4 Correct 28 ms 19248 KB Output is correct
5 Correct 23 ms 19292 KB Output is correct
6 Correct 24 ms 19028 KB Output is correct
7 Correct 198 ms 145200 KB Output is correct
8 Correct 538 ms 145476 KB Output is correct
9 Correct 317 ms 145316 KB Output is correct
10 Correct 471 ms 145564 KB Output is correct
11 Correct 350 ms 145428 KB Output is correct
12 Correct 307 ms 145540 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3164 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3316 KB Output is correct
4 Correct 28 ms 19248 KB Output is correct
5 Correct 23 ms 19292 KB Output is correct
6 Correct 24 ms 19028 KB Output is correct
7 Correct 205 ms 144212 KB Output is correct
8 Correct 571 ms 144720 KB Output is correct
9 Correct 341 ms 145048 KB Output is correct
10 Correct 468 ms 144640 KB Output is correct
11 Correct 418 ms 144824 KB Output is correct
12 Correct 365 ms 144724 KB Output is correct
13 Correct 198 ms 145200 KB Output is correct
14 Correct 538 ms 145476 KB Output is correct
15 Correct 317 ms 145316 KB Output is correct
16 Correct 471 ms 145564 KB Output is correct
17 Correct 350 ms 145428 KB Output is correct
18 Correct 307 ms 145540 KB Output is correct
19 Correct 214 ms 145876 KB Output is correct
20 Correct 574 ms 146812 KB Output is correct
21 Correct 320 ms 146208 KB Output is correct
22 Correct 451 ms 146728 KB Output is correct
23 Correct 332 ms 146260 KB Output is correct
24 Correct 351 ms 146404 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 144528 KB Output is correct
2 Correct 538 ms 144648 KB Output is correct
3 Correct 327 ms 144456 KB Output is correct
4 Correct 455 ms 144948 KB Output is correct
5 Correct 354 ms 144724 KB Output is correct
6 Correct 357 ms 144724 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 144528 KB Output is correct
2 Correct 538 ms 144648 KB Output is correct
3 Correct 327 ms 144456 KB Output is correct
4 Correct 455 ms 144948 KB Output is correct
5 Correct 354 ms 144724 KB Output is correct
6 Correct 357 ms 144724 KB Output is correct
7 Correct 223 ms 146800 KB Output is correct
8 Correct 530 ms 146844 KB Output is correct
9 Correct 313 ms 146688 KB Output is correct
10 Correct 583 ms 146888 KB Output is correct
11 Correct 325 ms 146696 KB Output is correct
12 Correct 354 ms 146924 KB Output is correct