Submission #232949

#	Time	Username	Problem	Language	Result	Execution time	Memory
232949		pedy4000	Svjetlost (COI18_svjetlost)	C++98	69 / 100	3075 ms	21072 KiB

Main

#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 (stderr)

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);
   ~~~~~^~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 0 / 31