oj.uz

Submission #490091

# Submission time Handle Problem Language Result Execution time Memory
490091 2021-11-25T14:09:45 Z rainboy Svjetlost (COI18_svjetlost) C++17
40 / 100
 3000 ms 9988 KB 
#include <math.h>
#include <stdio.h>

#define N	100000
#define M	(N * 8)

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 aa[M * 2]; int n_;

void update_(int i, double x) {
	aa[i] += x;
}

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);
}

double query() {
	int i;
	double a, ans;

	a = 0, ans = 0;
	for (i = 0; i < n_; i++)
		ans = max(ans, a += aa[i]);
	return ans;
}

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_;
	for (h = 0; h < n; h++)
		update(h, 1);
	printf("%f\n", query());
	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", query());
	}
	return 0;
}

Compilation message

svjetlost.cpp: In function 'int compare(int, int)':
svjetlost.cpp:34:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   34 |  sgn1 = xx_[h1] < 0 || xx_[h1] == 0 && yy_[h1] < 0 ? -1 : 1;
      |                        ~~~~~~~~~~~~~^~~~~~~~~~~~~~
svjetlost.cpp:35:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |  sgn2 = xx_[h2] < 0 || xx_[h2] == 0 && yy_[h2] < 0 ? -1 : 1;
      |                        ~~~~~~~~~~~~~^~~~~~~~~~~~~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   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 0 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 0 ms 332 KB 11 numbers
4 Correct 0 ms 332 KB 93 numbers
5 Correct 1 ms 332 KB 101 numbers
6 Correct 9 ms 592 KB 1201 numbers
7 Correct 13 ms 660 KB 1556 numbers
8 Correct 22 ms 716 KB 1996 numbers
9 Correct 20 ms 716 KB 1960 numbers
10 Correct 22 ms 752 KB 1991 numbers
11 Correct 20 ms 756 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 1 ms 456 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 7 ms 1148 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 13 ms 1904 KB found '31424400.0534060001', expected '31424400.0534067489', error '0.0000000000'
5 Correct 52 ms 7356 KB found '3142086769.6889638901', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 55 ms 7396 KB found '3142076120.8714489937', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 660 KB 1001 numbers
2 Correct 1202 ms 4320 KB 15001 numbers
3 Execution timed out 3096 ms 9988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
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 0 ms 332 KB 11 numbers
4 Correct 0 ms 332 KB 93 numbers
5 Correct 1 ms 332 KB 101 numbers
6 Correct 9 ms 592 KB 1201 numbers
7 Correct 13 ms 660 KB 1556 numbers
8 Correct 22 ms 716 KB 1996 numbers
9 Correct 20 ms 716 KB 1960 numbers
10 Correct 22 ms 752 KB 1991 numbers
11 Correct 20 ms 756 KB 1963 numbers
12 Correct 0 ms 288 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 1 ms 456 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 7 ms 1148 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 13 ms 1904 KB found '31424400.0534060001', expected '31424400.0534067489', error '0.0000000000'
16 Correct 52 ms 7356 KB found '3142086769.6889638901', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 55 ms 7396 KB found '3142076120.8714489937', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 10 ms 660 KB 1001 numbers
19 Correct 1202 ms 4320 KB 15001 numbers
20 Execution timed out 3096 ms 9988 KB Time limit exceeded
21 Halted 0 ms 0 KB -