oj.uz

Submission #232899

# Submission time Handle Problem Language Result Execution time Memory
232899 2020-05-18T16:00:45 Z pedy4000 Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 20368 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() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i].X >> p[i].Y;

	preProcess();
	cout << fixed << setprecision(6) << res[1] << "\n";
	cin >> q;
	while (q--) {
		int id;
		cin >> id;
		id--;

		delate(id);
		cout << res[1] << "\n";
	}
	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;
            ~~^~~

Subtask #1
12.0 / 12.0

# 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

Subtask #2
14.0 / 14.0

# 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 12 ms 512 KB 101 numbers
6 Correct 47 ms 640 KB 1201 numbers
7 Correct 63 ms 768 KB 1556 numbers
8 Correct 77 ms 768 KB 1996 numbers
9 Correct 64 ms 768 KB 1960 numbers
10 Correct 69 ms 888 KB 1991 numbers
11 Correct 62 ms 768 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 12 ms 640 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 117 ms 2296 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 243 ms 4060 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 1382 ms 15696 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 1435 ms 16076 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1016 KB 1001 numbers
2 Correct 1016 ms 5952 KB 15001 numbers
3 Correct 2921 ms 12048 KB 44445 numbers
4 Execution timed out 3069 ms 20368 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 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 12 ms 512 KB 101 numbers
6 Correct 47 ms 640 KB 1201 numbers
7 Correct 63 ms 768 KB 1556 numbers
8 Correct 77 ms 768 KB 1996 numbers
9 Correct 64 ms 768 KB 1960 numbers
10 Correct 69 ms 888 KB 1991 numbers
11 Correct 62 ms 768 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 12 ms 640 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 117 ms 2296 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 243 ms 4060 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 1382 ms 15696 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 1435 ms 16076 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 51 ms 1016 KB 1001 numbers
19 Correct 1016 ms 5952 KB 15001 numbers
20 Correct 2921 ms 12048 KB 44445 numbers
21 Execution timed out 3069 ms 20368 KB Time limit exceeded
22 Halted 0 ms 0 KB -