답안 #232921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232921 2020-05-18T16:37:54 Z pedy4000 Svjetlost (COI18_svjetlost) C++14
40 / 100
3000 ms 22856 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 <= 40);
	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);
   ~~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 44 ms 768 KB 1556 numbers
8 Correct 56 ms 768 KB 1996 numbers
9 Correct 43 ms 768 KB 1960 numbers
10 Correct 48 ms 768 KB 1991 numbers
11 Correct 42 ms 768 KB 1963 numbers
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 5 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 16504 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 73 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 1024 KB 1001 numbers
2 Correct 603 ms 6120 KB 15001 numbers
3 Correct 1719 ms 12408 KB 44445 numbers
4 Correct 1468 ms 20768 KB 22223 numbers
5 Execution timed out 3087 ms 22856 KB Time limit exceeded
# 결과 실행 시간 메모리 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 44 ms 768 KB 1556 numbers
8 Correct 56 ms 768 KB 1996 numbers
9 Correct 43 ms 768 KB 1960 numbers
10 Correct 48 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 5 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 16504 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 73 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 31 ms 1024 KB 1001 numbers
19 Correct 603 ms 6120 KB 15001 numbers
20 Correct 1719 ms 12408 KB 44445 numbers
21 Correct 1468 ms 20768 KB 22223 numbers
22 Execution timed out 3087 ms 22856 KB Time limit exceeded