Submission #232949

# Submission time Handle Problem Language Result Execution time Memory
232949 2020-05-18T18:10:59 Z pedy4000 Svjetlost (COI18_svjetlost) C++
69 / 100
3000 ms 21072 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];
int mn[N << 2];
int mx[N << 2];
 
int dist (int a, int b) {
 
	return a < b? b - a: n - a + b;
}
 
int nxt (int a, int s = 0, int e = n, int id = 1) {
	if (e - s == 1)
		return s;
	int mid = e + s >> 1;
	if (a < mx[id << 1])
		return nxt(a, s, mid, id << 1);
	if (a < mx[id << 1 | 1])
		return nxt(a, mid, e, id << 1 | 1);
	return nxt(-1, 0, n, 1);
}
 
int prv (int a, int s = 0, int e = n, int id = 1) {
	if (e - s == 1)
		return s;
	int mid = e + s >> 1;
	if (mn[id << 1 | 1] < a)
		return prv(a, mid, e, id << 1 | 1);
	if (mn[id << 1] < a)
		return prv(a, s, mid, id << 1);
	return prv(n, 0, n, 1);
}
 
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[e % n]);
		len[id] = LEN[s];
		mx[id] = mn[id] = 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];
	mx[id] = e - 1;
	mn[id] = s;
}
 
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() {
	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 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]) {
		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;
	}
 
	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]) {
		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;
	}
 
	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 fuck (int tmp, int s = 0, int e = n, int id = 1) {
	if (e - s == 1) {
		mn[id] = 1000000000, mx[id] = -1000000000;
		return ;
	}
	int mid = e + s >> 1;
	if (tmp < mid)
		fuck(tmp, s, mid, id << 1);
	else
		fuck(tmp, mid, e, id << 1 | 1);
	mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}
 
void delate (int id) {
	K2 = calcRev(prv(id));
	fuck(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 'int nxt(int, int, int, int)':
svjetlost.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'int prv(int, int, int, int)':
svjetlost.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'ld getLen(int, int, int, int, int)':
svjetlost.cpp:81: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:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildLen(int, int, int)':
svjetlost.cpp:148:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildResLst(int, int, int)':
svjetlost.cpp:162: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:200: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:226:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void fuck(int, int, int, int)':
svjetlost.cpp:246:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'int main()':
svjetlost.cpp:281:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
svjetlost.cpp:283: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:287:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
svjetlost.cpp:290: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 5 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 5 ms 384 KB 93 numbers
5 Correct 7 ms 512 KB 101 numbers
6 Correct 27 ms 640 KB 1201 numbers
7 Correct 34 ms 640 KB 1556 numbers
8 Correct 47 ms 888 KB 1996 numbers
9 Correct 35 ms 768 KB 1960 numbers
10 Correct 38 ms 760 KB 1991 numbers
11 Correct 35 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 5 ms 640 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 10 ms 2176 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 14 ms 3968 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 46 ms 14584 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 46 ms 14588 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
# Verdict Execution time Memory Grader output
1 Correct 23 ms 896 KB 1001 numbers
2 Correct 358 ms 5308 KB 15001 numbers
3 Correct 1029 ms 10848 KB 44445 numbers
4 Correct 707 ms 19040 KB 22223 numbers
5 Correct 2101 ms 21072 KB 88889 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 5 ms 384 KB 93 numbers
5 Correct 7 ms 512 KB 101 numbers
6 Correct 27 ms 640 KB 1201 numbers
7 Correct 34 ms 640 KB 1556 numbers
8 Correct 47 ms 888 KB 1996 numbers
9 Correct 35 ms 768 KB 1960 numbers
10 Correct 38 ms 760 KB 1991 numbers
11 Correct 35 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 10 ms 2176 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 14 ms 3968 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 46 ms 14584 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 46 ms 14588 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 23 ms 896 KB 1001 numbers
19 Correct 358 ms 5308 KB 15001 numbers
20 Correct 1029 ms 10848 KB 44445 numbers
21 Correct 707 ms 19040 KB 22223 numbers
22 Correct 2101 ms 21072 KB 88889 numbers
23 Execution timed out 3075 ms 20848 KB Time limit exceeded
24 Halted 0 ms 0 KB -