oj.uz

답안 #232903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232903 2020-05-18T16:08:30 Z pedy4000 Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 18304 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#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;
point p[N];
ld res[N << 2];
ld lazy[N << 2];
ld len[N << 2];
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 s = nxt(d), e = 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[d], p[nxt(d)], p[mid], p[nxt(mid)]))
			s = mid;
		else
			e = mid;
	}
	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[id] = distance(p[s], p[nxt(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] = calcLen(s, calc(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();
	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) {
	int K2 = calcRev(prv(id));
	live.erase(id);
	int fr = nxt(id);
	int bc = prv(id);
	int K = calcRev(id);

	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), - distance(p[bc], p[id]) - distance(p[id], p[fr]) + distance(p[bc], p[fr]));
	if (calcRev(bc) != K)
		calcRes(calcRev(bc),  prv(K), - distance(p[bc], p[id]) + distance(p[bc], p[fr]));
	if (K2 != calcRev(bc))
		calcRes(K2, prv(calcRev(bc)), - distance(p[bc], p[id]));
}

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:67: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:76:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildLen(int, int, int)':
svjetlost.cpp:129:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildResLst(int, int, int)':
svjetlost.cpp:141: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:172: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:192:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:229:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
svjetlost.cpp:231: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:235:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
svjetlost.cpp:238:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &id);
   ~~~~~^~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 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 13 ms 512 KB 101 numbers
6 Correct 50 ms 640 KB 1201 numbers
7 Correct 62 ms 640 KB 1556 numbers
8 Correct 79 ms 640 KB 1996 numbers
9 Correct 65 ms 640 KB 1960 numbers
10 Correct 68 ms 640 KB 1991 numbers
11 Correct 62 ms 640 KB 1963 numbers

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 13 ms 512 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 113 ms 2040 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 240 ms 3624 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 1402 ms 14028 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 1406 ms 13968 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 888 KB 1001 numbers
2 Correct 1037 ms 5164 KB 15001 numbers
3 Correct 2896 ms 10540 KB 44445 numbers
4 Execution timed out 3075 ms 18304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 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 13 ms 512 KB 101 numbers
6 Correct 50 ms 640 KB 1201 numbers
7 Correct 62 ms 640 KB 1556 numbers
8 Correct 79 ms 640 KB 1996 numbers
9 Correct 65 ms 640 KB 1960 numbers
10 Correct 68 ms 640 KB 1991 numbers
11 Correct 62 ms 640 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 13 ms 512 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 113 ms 2040 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 240 ms 3624 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 1402 ms 14028 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 1406 ms 13968 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 51 ms 888 KB 1001 numbers
19 Correct 1037 ms 5164 KB 15001 numbers
20 Correct 2896 ms 10540 KB 44445 numbers
21 Execution timed out 3075 ms 18304 KB Time limit exceeded
22 Halted 0 ms 0 KB -