Submission #232923

# Submission time Handle Problem Language Result Execution time Memory
232923 2020-05-18T16:39:27 Z pedy4000 Svjetlost (COI18_svjetlost) C++14
40 / 100
3000 ms 22636 KB
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> point;
#define X first
#define Y second

point operator- (point a, point b) {

	return point(a.X - b.X, a.Y - b.Y);
}
ll operator* (point a, point b) {

	return a.X * b.Y - a.Y * b.X;
}
bool intersect (point a, point b, point c, point d) {
	point v = b - a, u = c - d;
	if (u * v == 0)
		return false;

	if (0 < (u * v))
		return (u * v) <= ((a - d) * v);
	return (u * v) >= ((a - d) * v);
}
ld distance (point a, point b) {

	return sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y));
}

const ll N = 1e5 + 5, inf = 10000000LL * 10000000LL;
int n, q, K, K2, K3, fr, bc;
point p[N];
ld res[N << 2], l1, l2;
ld RES[N];
ld lazy[N << 2];
ld len[N << 2];
ld LEN[N];
set <int> live;


int dist (int a, int b) {

	return a < b? b - a: n - a + b;
}

int nxt (int a) {
	if (live.lower_bound(a + 1) != live.end())
		return *live.lower_bound(a + 1);
	return *live.begin();
}

int prv (int a) {
	if (live.lower_bound(a) != live.begin())
		return *(--live.lower_bound(a));
	return *(--live.end());
}

ld getLen (int l, int r, int s = 0, int e = n, int id = 1) {
	if (l <= s && e <= r)
		return len[id];
	if (r <= s || e <= l)
		return 0;
	int mid = e + s >> 1;
	return getLen(l, r, s, mid, id << 1) + getLen(l, r, mid, e, id << 1 | 1);
}

void updLen (int tmp, ld val, int s = 0, int e = n, int id = 1) {
	if (e - s == 1) {
		len[id] = val;
		return ;
	}
	int mid = e + s >> 1;
	if (tmp < mid)
		updLen(tmp, val, s, mid, id << 1);
	else
		updLen(tmp, val, mid, e, id << 1 | 1);
	len[id] = len[id << 1] + len[id << 1 | 1];
}

ld calcLen (int l, int r) {
	if (l <= r)
		return getLen(l, r + 1);
	return getLen(l, n) + getLen(0, r + 1);
}

int calc (int d) {
	int cnt = 0;
	int s = nxt(d), e = d;
	while (nxt(s) != e) {
		cnt++;
		int mid = (s + dist(s, e) / 2) % n;
		if (nxt(mid) == e)
			mid = prv(nxt(mid));
		else
			mid = nxt(prv(mid));

		if (intersect(p[d], p[nxt(d)], p[mid], p[nxt(mid)]))
			s = mid;
		else
			e = mid;
	}
	assert(cnt <= 20);
	return s;
}

int calcRev (int d) {
	int s = d, e = prv(d);
	while (nxt(s) != e) {
		int mid = (s + dist(s, e) / 2) % n;
		if (nxt(mid) == e)
			mid = prv(nxt(mid));
		else
			mid = nxt(prv(mid));
		if (intersect(p[mid], p[nxt(mid)], p[d], p[nxt(d)]))
			e = mid;
		else
			s = mid;
	}
	return e;
}

void buildLen (int s = 0, int e = n, int id = 1) {
	if (e - s == 1) {
		LEN[s] = distance(p[s], p[nxt(s)]);
		len[id] = LEN[s];
		return ;
	}

	int mid = e + s >> 1;
	buildLen(s, mid, id << 1);
	buildLen(mid, e, id << 1 | 1);
	len[id] = len[id << 1] + len[id << 1 | 1];
}

void buildResLst (int s = 0, int e = n, int id = 1) {
	if (e - s == 1) {
		res[id] = RES[s];
		return ;
	}

	int mid = e + s >> 1;
	buildResLst(s, mid, id << 1);
	buildResLst(mid, e, id << 1 | 1);
	res[id] = max(res[id << 1], res[id << 1 | 1]);
}

void preProcess() {
	for (int i = 0; i < n; i++)
		live.insert(i);
	buildLen();
	int r = 1;
	ld sum = LEN[0];
	for (int l = 0; l < n; l++) {
		while (intersect(p[l], p[(l + 1) % n], p[r], p[(r + 1) % n])) {
			sum += LEN[r];
			r = (r + 1) % n;
		}

		RES[l] = sum;
		sum -= LEN[l];
	}

	buildResLst();
}

void shift (int id) {
	res[id << 1] += lazy[id];
	lazy[id << 1] += lazy[id];
	res[id << 1 | 1] += lazy[id];
	lazy[id << 1 | 1] += lazy[id];

	lazy[id] = 0;
}

void setRes (int tmp, ld val, int s = 0, int e = n, int id = 1) {
	if (e - s == 1) {
		res[id] = val;
		return ;
	}

	if (lazy[id])
		shift(id);

	int mid = e + s >> 1;
	if (tmp < mid)
		setRes(tmp, val, s, mid, id << 1);
	else
		setRes(tmp, val, mid, e, id << 1 | 1);
	res[id] = max(res[id << 1], res[id << 1 | 1]);
}

void updRes (int l, int r, ld val, int s = 0, int e = n, int id = 1) {
	if (l <= s && e <= r) {
		res[id] += val;
		lazy[id] += val;
		return ;
	}
	if (r <= s || e <= l)
		return ;

	if (lazy[id])
		shift(id);

	int mid = e + s >> 1;
	updRes(l, r, val, s, mid, id << 1);
	updRes(l, r, val, mid, e, id << 1 | 1);
	res[id] = max(res[id << 1], res[id << 1 | 1]);
}

void calcRes (int l, int r, ld val) {
	if (l <= r)
		updRes(l, r + 1, val);
	else {
		updRes(l, n, val);
		updRes(0, r + 1, val);
	}
}

void delate (int id) {
	K2 = calcRev(prv(id));
	live.erase(id);
	fr = nxt(id);
	bc = prv(id);
	K = calcRev(id);
	K3 = calcRev(bc);
	l1 = distance(p[bc], p[id]);
	l2 = distance(p[bc], p[fr]);

	updLen(id, 0);
	updLen(bc, distance(p[bc], p[fr]));

	setRes(id, -inf);
	setRes(bc, calcLen(bc, calc(bc)));

	if (K != bc)
		calcRes(K, prv(bc), - l1 - distance(p[id], p[fr]) + l2);
	if (K3 != K)
		calcRes(K3, prv(K), - l1 + l2);
	if (K2 != K3)
		calcRes(K2, prv(K3), - l1);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld %lld", &p[i].X, &p[i].Y);

	preProcess();
	printf("%5LF\n", res[1]);
	scanf("%d", &q);
	while (q--) {
		int id;
		scanf("%d", &id);
		id--;

		delate(id);
	printf("%5LF\n", res[1]);
	}
	return 0;
}

Compilation message

svjetlost.cpp: In function 'ld getLen(int, int, int, int, int)':
svjetlost.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void updLen(int, ld, int, int, int)':
svjetlost.cpp:80:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildLen(int, int, int)':
svjetlost.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildResLst(int, int, int)':
svjetlost.cpp:149:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void setRes(int, ld, int, int, int)':
svjetlost.cpp:192:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void updRes(int, int, ld, int, int, int)':
svjetlost.cpp:212:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:252:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
svjetlost.cpp:254:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &p[i].X, &p[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
svjetlost.cpp:258:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
svjetlost.cpp:261:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &id);
   ~~~~~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 6 ms 384 KB 93 numbers
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 6 ms 384 KB 93 numbers
5 Correct 8 ms 512 KB 101 numbers
6 Correct 35 ms 640 KB 1201 numbers
7 Correct 46 ms 768 KB 1556 numbers
8 Correct 59 ms 768 KB 1996 numbers
9 Correct 45 ms 768 KB 1960 numbers
10 Correct 47 ms 768 KB 1991 numbers
11 Correct 42 ms 768 KB 1963 numbers
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 6 ms 640 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 13 ms 2432 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 20 ms 4344 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 77 ms 16632 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 77 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
# Verdict Execution time Memory Grader output
1 Correct 36 ms 1024 KB 1001 numbers
2 Correct 576 ms 6136 KB 15001 numbers
3 Correct 1700 ms 12024 KB 44445 numbers
4 Correct 1405 ms 20788 KB 22223 numbers
5 Execution timed out 3083 ms 22636 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 6 ms 384 KB 93 numbers
5 Correct 8 ms 512 KB 101 numbers
6 Correct 35 ms 640 KB 1201 numbers
7 Correct 46 ms 768 KB 1556 numbers
8 Correct 59 ms 768 KB 1996 numbers
9 Correct 45 ms 768 KB 1960 numbers
10 Correct 47 ms 768 KB 1991 numbers
11 Correct 42 ms 768 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 6 ms 640 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 13 ms 2432 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 20 ms 4344 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 77 ms 16632 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 77 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 36 ms 1024 KB 1001 numbers
19 Correct 576 ms 6136 KB 15001 numbers
20 Correct 1700 ms 12024 KB 44445 numbers
21 Correct 1405 ms 20788 KB 22223 numbers
22 Execution timed out 3083 ms 22636 KB Time limit exceeded