oj.uz

Submission #490092

# Submission time Handle Problem Language Result Execution time Memory
490092 2021-11-25T14:12:55 Z rainboy Svjetlost (COI18_svjetlost) C++17
100 / 100
 545 ms 31100 KB 
#include <math.h>
#include <stdio.h>

#define N	100000
#define M	(N * 8)
#define N_	(1 << 21)	/* N_ = pow2(ceil(log2(M * 2))) */

double max(double a, double b) { return a > b ? a : b; }

unsigned int X = 12345;

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

int xx[N], yy[N], n;

long long cross(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

int xx_[M * 2], yy_[M * 2], hh[M * 2], ii[M * 2], m;

void add(int i, int j) {
	int h = m++;

	xx_[h << 1 | 0] = xx[i] - xx[j], yy_[h << 1 | 0] = yy[i] - yy[j];
	xx_[h << 1 | 1] = xx[j] - xx[i], yy_[h << 1 | 1] = yy[j] - yy[i];
}

int compare(int h1, int h2) {
	int sgn1, sgn2;
	long long c;

	sgn1 = xx_[h1] < 0 || xx_[h1] == 0 && yy_[h1] < 0 ? -1 : 1;
	sgn2 = xx_[h2] < 0 || xx_[h2] == 0 && yy_[h2] < 0 ? -1 : 1;
	if (sgn1 != sgn2)
		return sgn1 - sgn2;
	c = cross(xx_[h1], yy_[h1], xx_[h2], yy_[h2]);
	return c == 0 ? 0 : c < 0 ? -1 : 1;
}

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 = compare(hh[j], 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;
	}
}

double sum[N_ * 2], pref[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	sum[i] = sum[l] + sum[r];
	pref[i] = max(pref[l], sum[l] + pref[r]);
}

void update_(int i, double x) {
	i += n_;
	pref[i] = sum[i] += x;
	while (i > 1)
		pul(i >>= 1);
}

void update(int h, int w) {
	int h0 = h << 1, h1 = h0 | 1;
	double d = hypot(xx_[h0], yy_[h0]);

	update_(ii[h0], d * w), update_(ii[h1], -d * w);
	if (ii[h0] > ii[h1])
		update_(0, d * w);
}

int main() {
	static int uu[N], vv[N];
	int q, h, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++)
		uu[i] = (i - 1 + n) % n, vv[i] = (i + 1) % n;
	for (i = 0; i < n; i++)
		add(i, vv[i]);
	scanf("%d", &q);
	for (h = 0; h < q; h++) {
		int u, v;

		scanf("%d", &i), i--;
		u = uu[i], v = vv[i];
		add(u, i), add(i, v), add(u, v);
		vv[u] = v, uu[v] = u;
	}
	for (h = 0; h < m * 2; h++)
		hh[h] = h;
	sort(hh, 0, m * 2);
	for (h = 0, n_ = 0; h < m * 2; h++)
		ii[hh[h]] = h + 1 == m * 2 || compare(hh[h + 1], hh[h]) != 0 ? n_++ : n_;
	while ((n_ & n_ - 1) != 0)
		n_++;
	for (h = 0; h < n; h++)
		update(h, 1);
	printf("%f\n", pref[1]);
	for (h = 0; h < q; h++) {
		update(n + h * 3 + 0, -1), update(n + h * 3 + 1, -1), update(n + h * 3 + 2, 1);
		printf("%f\n", pref[1]);
	}
	return 0;
}

Compilation message

svjetlost.cpp: In function 'int compare(int, int)':
svjetlost.cpp:35:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |  sgn1 = xx_[h1] < 0 || xx_[h1] == 0 && yy_[h1] < 0 ? -1 : 1;
      |                        ~~~~~~~~~~~~~^~~~~~~~~~~~~~
svjetlost.cpp:36:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |  sgn2 = xx_[h2] < 0 || xx_[h2] == 0 && yy_[h2] < 0 ? -1 : 1;
      |                        ~~~~~~~~~~~~~^~~~~~~~~~~~~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:115:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  115 |  while ((n_ & n_ - 1) != 0)
      |               ~~~^~~
svjetlost.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d", &i), i--;
      |   ~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB 11 numbers
2 Correct 0 ms 332 KB 41 numbers
3 Correct 1 ms 332 KB 11 numbers
4 Correct 0 ms 332 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB 11 numbers
2 Correct 0 ms 332 KB 41 numbers
3 Correct 1 ms 332 KB 11 numbers
4 Correct 0 ms 332 KB 93 numbers
5 Correct 1 ms 460 KB 101 numbers
6 Correct 4 ms 716 KB 1201 numbers
7 Correct 5 ms 716 KB 1556 numbers
8 Correct 7 ms 884 KB 1996 numbers
9 Correct 6 ms 844 KB 1960 numbers
10 Correct 6 ms 844 KB 1991 numbers
11 Correct 6 ms 844 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 460 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 11 ms 1612 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 19 ms 2636 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 98 ms 9640 KB found '3142086769.6889748573', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 101 ms 9660 KB found '3142076120.8714489937', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 716 KB 1001 numbers
2 Correct 71 ms 5520 KB 15001 numbers
3 Correct 196 ms 13588 KB 44445 numbers
4 Correct 168 ms 15036 KB 22223 numbers
5 Correct 417 ms 28664 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB 11 numbers
2 Correct 0 ms 332 KB 41 numbers
3 Correct 1 ms 332 KB 11 numbers
4 Correct 0 ms 332 KB 93 numbers
5 Correct 1 ms 460 KB 101 numbers
6 Correct 4 ms 716 KB 1201 numbers
7 Correct 5 ms 716 KB 1556 numbers
8 Correct 7 ms 884 KB 1996 numbers
9 Correct 6 ms 844 KB 1960 numbers
10 Correct 6 ms 844 KB 1991 numbers
11 Correct 6 ms 844 KB 1963 numbers
12 Correct 1 ms 332 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 2 ms 460 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 11 ms 1612 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 19 ms 2636 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 98 ms 9640 KB found '3142086769.6889748573', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 101 ms 9660 KB found '3142076120.8714489937', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 5 ms 716 KB 1001 numbers
19 Correct 71 ms 5520 KB 15001 numbers
20 Correct 196 ms 13588 KB 44445 numbers
21 Correct 168 ms 15036 KB 22223 numbers
22 Correct 417 ms 28664 KB 88889 numbers
23 Correct 545 ms 31032 KB 98175 numbers
24 Correct 113 ms 8180 KB 25905 numbers
25 Correct 533 ms 31100 KB 98169 numbers
26 Correct 441 ms 29056 KB 91845 numbers
27 Correct 479 ms 31064 KB 98296 numbers
28 Correct 438 ms 26976 KB 85384 numbers
29 Correct 414 ms 26988 KB 85317 numbers
30 Correct 483 ms 31048 KB 98246 numbers
31 Correct 255 ms 19784 KB 50001 numbers